C. Recycling Bottles time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output
It was recycling day in Kekoland. To celebrate it Adil and Bera went to Central Perk where they can take bottles from the ground and put them into a recycling bin.
We can think Central Perk as coordinate plane. There are n bottles on the ground, the i-th bottle is located at position (xi, yi). Both Adil and Bera can carry only one bottle at once each.
For both Adil and Bera the process looks as follows:
- Choose to stop or to continue to collect bottles.
- If the choice was to continue then choose some bottle and walk towards it.
- Pick this bottle and walk to the recycling bin.
- Go to step 1.
Adil and Bera may move independently. They are allowed to pick bottles simultaneously, all bottles may be picked by any of the two, it's allowed that one of them stays still while the other one continues to pick bottles.
They want to organize the process such that the total distance they walk (the sum of distance walked by Adil and distance walked by Bera) is minimum possible. Of course, at the end all bottles should lie in the recycling bin.
Input
First line of the input contains six integers ax, ay, bx, by, tx and ty (0 ≤ ax, ay, bx, by, tx, ty ≤ 109) — initial positions of Adil, Bera and recycling bin respectively.
The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of bottles on the ground.
Then follow n lines, each of them contains two integers xi and yi (0 ≤ xi, yi ≤ 109) — position of the i-th bottle.
It's guaranteed that positions of Adil, Bera, recycling bin and all bottles are distinct.
Output
Print one real number — the minimum possible total distance Adil and Bera need to walk in order to put all bottles into recycling bin. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct if
.
Examples Input
3 1 1 2 0 0
3
1 1
2 1
2 3
Output
11.084259940083
Input
5 0 4 2 2 0
5
5 2
3 0
5 5
3 5
3 3
Output
33.121375178000
Note
Consider the first sample.
Adil will use the following path:
.
Bera will use the following path:
.
Adil's path will be
units long, while Bera's path will be
units long.
題目大意：
現在有兩個人，分别站在（ax，ay）和（bx，by）處，現在有N個垃圾，需要處理，垃圾箱位于（tx，ty）處，這兩個人每次隻能拿一個垃圾，并且拿到垃圾之後必須放到垃圾箱中，對于兩個人來講，每個人的行動都是相對獨立的。問兩個人的路徑和最小是多少，就能夠将所有垃圾都扔到垃圾箱中。
思路：
1、這種思維題還是靠某些典型題的體型所影響。比如51nod 1487 占領資源（topcoder上的題）這道題：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1487
利用到這種極限思維的題還是蠻經典的。可以規劃到一類去深刻記憶。
因為做出來這個題的時候感覺這種極限思維還是蠻有趣的，記憶比較深刻。
2、對于A.B兩個人來講，如果一開始都在垃圾箱處出發，那麼ans=2*Σdis（xi，yi）---->（tx，ty）；
對于兩個人A.B，每個人隻要都選了一個垃圾去撿，并且都回到了垃圾箱處，那麼接下來的路程就相當于一個人來回走。
那麼對于暴力思維來講，那就是直接O（n^2）枚舉兩個垃圾，過程維護最小值。顯然這麼做是會逾時的。
那麼接下裡從貪心的角度出發，對于ans=2*Σdis（xi，yi）->（tx，ty）-A選擇的第一個垃圾的點到垃圾箱的距離+A選擇的第一個垃圾的點到A初始位子的距離-B選擇的第一個垃圾的點到垃圾箱的距離+B選擇的第一個垃圾的點到A初始位子的距離；
我們肯定是希望後邊這一大長串描述中，A選擇的第一個垃圾的點到A初始位子的距離以及B選擇的第一個垃圾的點到B初始位子的距離的和盡可能的小，然而對于不同的選擇方式，最終答案肯定是不同的。
那麼我們不妨設定兩個數組A【】，B【】，一個按照點與A的距離從小到大排序，一個按照與B的距離從小到大排序。
接下來我們可以暴力枚舉兩項，分别作為A選擇的點以及B選擇的點，當然不能忘記，有可能一個人一直不動是正解，這種情況也要枚舉。
3、通過思考和簡單枚舉不難發現對于枚舉的量，其實隻要足夠大，就一定不會影響結果。
是以在第一次送出的時候，我A，B數組都枚舉了1000的量，結果是Ac的。（再之後交了一發100的枚舉量，也是Ac的）；
4、這種極限思維還是蠻實用的。
Ac代碼：
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll __int64
struct node
{
ll x,y;
double dis0;
double disa;
double disb;
int pos;
}a[100060],b[100060];
double dis(ll a,ll b,ll c,ll d)
{
return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int cmp(node a,node b)
{
if(a.disa!=b.disa)
return a.disa<b.disa;
else return a.disb<b.disb;
}
int cmp2(node a,node b)
{
if(a.disb!=b.disb)
return a.disb<b.disb;
else return a.disa<b.disa;
}
int main()
{
ll ax,ay,bx,by,tx,ty;
while(~scanf("%I64d%I64d%I64d%I64d%I64d%I64d",&ax,&ay,&bx,&by,&tx,&ty))
{
ll n;
scanf("%I64d",&n);
double minna=-1,minna0;
double minnb=-1,minnb0;
double sum=0;
for(int i=0;i<n;i++)
{
scanf("%I64d%I64d",&a[i].x,&a[i].y);
a[i].pos=i;
b[i].pos=i;
a[i].dis0=dis(a[i].x,a[i].y,tx,ty);
a[i].disa=dis(a[i].x,a[i].y,ax,ay);
a[i].disb=dis(a[i].x,a[i].y,bx,by);
sum+=2*a[i].dis0;
b[i].dis0=a[i].dis0,b[i].disa=a[i].disa;b[i].disb=a[i].disb;
}
double ans=2000000000000000000;
sort(a,a+n,cmp);
sort(b,b+n,cmp2);
for(int i=0;i<n&&i<100;i++)
{
for(int j=0;j<n&&j<100;j++)
{
if(a[i].pos==b[j].pos)
{
ans=min(ans,min(sum-a[i].dis0+a[i].disa,sum-b[j].dis0+b[j].disb));
continue;
}
ans=min(ans,sum-a[i].dis0-b[j].dis0+a[i].disa+b[j].disb);
}
}
printf("%.12lf\n",ans);
}
}