codeforces#352-C-Recycling Bottles-欲張り

http://codeforces.com/contest/672/problem/C
タイトル通り、誰かが初めて拾った後、原点に戻った後、後の操作の距離はすべて原点から各点までの距離です.
従ってsum=各点から原点Tまでの距離を直接前処理する
そして、各点からaまでの距離、bまでの距離を前処理する
明らかに時間を節約するには、aの最初のステップが時間を節約できるかどうかを見て、最大の(dis(a,i)- dis(t,i ))
b同理.
 
だから案はaだけを選ぶ
bのみ選択
a,bはすべて選択する

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.00000001;

int n;
struct node
{
    double x,y;
    int id;
    double val;
    int type;
};
node tt[100005];
node bb[100005];
double xx[100005];
double yy[100005];
bool cmp(node a,node b)
{
    return a.val>b.val;
}
int main()
{

    double  ax,ay,bx,by,tx,ty;

    cin>>ax>>ay>>bx>>by>>tx>>ty;
    cin>>n;
    double x,y;
    double sum=0;
    int ok=0,bok=0;;
    int i,j;
    double sta=sqrt((ax-tx)*(ax-tx)+(ay-ty)*(ay-ty) );
    double stb=sqrt((bx-tx)*(bx-tx)+(by-ty)*(by-ty) );
    for (  i=1; i<=n; i++)
    {
        scanf("%lf%lf",&xx[i],&yy[i]);
        double dis=sqrt((xx[i]-tx)*(xx[i]-tx)+(yy[i]-ty)*(yy[i]-ty));
        double disa=sqrt((xx[i]-ax)*(xx[i]-ax)+(yy[i]-ay)*(yy[i]-ay));
        double disb=sqrt((xx[i]-bx)*(xx[i]-bx)+(yy[i]-by)*(yy[i]-by));
        sum+=2* dis;
        ++ok;
        tt[ok].id=i;
        tt[ok].val=dis- disa;  //  time
        ++bok;
        bb[bok].id=i;
        bb[bok].val=dis- disb;
    }
    sort(bb+1,bb+1+bok,cmp);
    sort(tt+1,tt+1+ok,cmp);

    int hasreturn=0;
    double ansa=sum-tt[1].val;
    double ansb=sum-bb[1].val;

   double ansc=1e18;
   if (tt[1].id!=bb[1].id)
    ansc=sum-tt[1].val-bb[1].val;
   else
    if (n>1)
    ansc=min(sum-tt[1].val-bb[2].val
    , sum-tt[2].val-bb[1].val);

    printf("%.6lf
",min(ansa,min(ansc,ansb)));













    return 0;

}