首页 > 代码库 > CodeForces 671A Recycling Bottles

CodeForces 671A Recycling Bottles

 

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c=getchar(); x=0;    while(!isdigit(c)) c=getchar();    while(isdigit(c)) {x=x*10+c-0; c=getchar();}}const int maxn=100010;double ax,ay,bx,by,tx,ty;struct X{ double x,y;int id; }s[maxn];int n;bool cmp1(X a,X b){    return sqrt((a.x-ax)*(a.x-ax)+(a.y-ay)*(a.y-ay))-sqrt((a.x-tx)*(a.x-tx)+(a.y-ty)*(a.y-ty))            <            sqrt((b.x-ax)*(b.x-ax)+(b.y-ay)*(b.y-ay))-sqrt((b.x-tx)*(b.x-tx)+(b.y-ty)*(b.y-ty));}bool cmp2(X a,X b){    return sqrt((a.x-bx)*(a.x-bx)+(a.y-by)*(a.y-by))-sqrt((a.x-tx)*(a.x-tx)+(a.y-ty)*(a.y-ty))            <            sqrt((b.x-bx)*(b.x-bx)+(b.y-by)*(b.y-by))-sqrt((b.x-tx)*(b.x-tx)+(b.y-ty)*(b.y-ty));}bool cmp3(X a,X b){    return a.id<b.id;}int a[maxn],sz;int main(){    scanf("%lf%lf%lf%lf%lf%lf",&ax,&ay,&bx,&by,&tx,&ty);    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%lf%lf",&s[i].x,&s[i].y),s[i].id=i;    if(n==1)    {        double ans;        ans=min(sqrt((ax-s[1].x)*(ax-s[1].x)+(ay-s[1].y)*(ay-s[1].y))+                sqrt((tx-s[1].x)*(tx-s[1].x)+(ty-s[1].y)*(ty-s[1].y))                ,                sqrt((bx-s[1].x)*(bx-s[1].x)+(by-s[1].y)*(by-s[1].y))+                sqrt((tx-s[1].x)*(tx-s[1].x)+(ty-s[1].y)*(ty-s[1].y))                );        printf("%.6lf\n",ans);        return 0;    }    double ans=999999999999999999;    double g=0;    for(int i=1;i<=n;i++) g=g+2*sqrt((s[i].x-tx)*(s[i].x-tx)+(s[i].y-ty)*(s[i].y-ty));    sort(s+1,s+1+n,cmp1);    ans=min(ans,            g+sqrt((s[1].x-ax)*(s[1].x-ax)+(s[1].y-ay)*(s[1].y-ay))            -sqrt((s[1].x-tx)*(s[1].x-tx)+(s[1].y-ty)*(s[1].y-ty)));    for(int i=1;i<=min(n,2);i++) a[sz++]=s[i].id;    sort(s+1,s+1+n,cmp2);    ans=min(ans,            g+sqrt((s[1].x-bx)*(s[1].x-bx)+(s[1].y-by)*(s[1].y-by))            -sqrt((s[1].x-tx)*(s[1].x-tx)+(s[1].y-ty)*(s[1].y-ty)));    for(int i=1;i<=min(n,2);i++) a[sz++]=s[i].id;        sort(s+1,s+1+n,cmp3);    for(int i=0; i<sz; i++)    {        for(int j=0; j<sz; j++)        {            if(a[j]==a[i]) continue;            double tmp=g;            tmp=tmp+sqrt((s[a[i]].x-ax)*(s[a[i]].x-ax)+(s[a[i]].y-ay)*(s[a[i]].y-ay));            tmp=tmp+sqrt((s[a[j]].x-bx)*(s[a[j]].x-bx)+(s[a[j]].y-by)*(s[a[j]].y-by));            tmp=tmp-sqrt((s[a[i]].x-tx)*(s[a[i]].x-tx)+(s[a[i]].y-ty)*(s[a[i]].y-ty));            tmp=tmp-sqrt((s[a[j]].x-tx)*(s[a[j]].x-tx)+(s[a[j]].y-ty)*(s[a[j]].y-ty));            ans=min(ans,tmp);        }    }    printf("%.6lf\n",ans);    return 0;}

 

CodeForces 671A Recycling Bottles