【模拟】Codeforces 671A Recycling Bottles

时间：2023-03-09 01:35:14
【模拟】Codeforces 671A Recycling Bottles

题目链接：

　　http://codeforces.com/problemset/problem/671/A

题目大意：

　　A和B在一张二维平面上，平面上有N个垃圾，垃圾桶只有一个在T，问把所有垃圾全扔进垃圾桶最少走多远。一次只能拿一个垃圾。允许一个人走另一个人停下来。

　　(1 ≤ n ≤ 100 000)  (0 ≤ xi, yi ≤ 109)

题目思路：

　　【模拟】

　　因为每次只能携带一个垃圾，大部分垃圾都是人扔完上一个垃圾后，从垃圾桶出发去捡的。

　　而最多有两个垃圾不是被人从垃圾桶出发完再扔到垃圾桶。

　　可以先将答案算作都从垃圾桶开始往返捡的距离，再枚举哪一个垃圾被人直接走过去捡能优化答案。注意不要让两个人都选择同一个垃圾。

 //

 //by coolxxx

 //#include<bits/stdc++.h>

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<iomanip>

 #include<map>

 #include<memory.h>

 #include<time.h>

 #include<stdio.h>

 #include<stdlib.h>

 #include<string.h>

 //#include<stdbool.h>

 #include<math.h>

 #define min(a,b) ((a)<(b)?(a):(b))

 #define max(a,b) ((a)>(b)?(a):(b))

 #define abs(a) ((a)>0?(a):(-(a)))

 #define lowbit(a) (a&(-a))

 #define sqr(a) ((a)*(a))

 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b))

 #define mem(a,b) memset(a,b,sizeof(a))

 #define eps (1e-8)

 #define J 10

 #define mod 1000000007

 #define MAX 0x7f7f7f7f

 #define PI 3.14159265358979323

 #define N 100004

 using namespace std;

 typedef long long LL;

 int cas,cass;

 int n,m,lll,ans;

 double anss;

 struct xxx

 {

     LL x,y;

     double disa,disb,dist;

 }q[N],a,b,t;

 double dis(xxx aa,xxx bb)

 {

     return sqrt(sqr(aa.x-bb.x)+sqr(aa.y-bb.y));

 }

 bool cmp(xxx aa,xxx bb)

 {

     return aa.dist<bb.dist;

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

     freopen("1.txt","r",stdin);

 //    freopen("2.txt","w",stdout);

     #endif

     int i,j,ma,mb;

     double ax,ay,bx,by,z;

 //    for(scanf("%d",&cas);cas;cas--)

 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)

     while(~scanf("%I64d",&a.x))

 //    while(~scanf("%d",&n))

     {

         anss=;ay=by=;

         scanf("%I64d%I64d%I64d%I64d%I64d",&a.y,&b.x,&b.y,&t.x,&t.y);

         scanf("%d",&n);

         for(i=;i<=n;i++)

         {

             scanf("%I64d%I64d",&q[i].x,&q[i].y);

             q[i].disa=dis(a,q[i]);

             q[i].disb=dis(b,q[i]);

             q[i].dist=dis(t,q[i]);

         }

         sort(q+,q++n,cmp);

         anss=q[].dist+q[].dist;

         ax=q[].dist-q[].disa;

         bx=q[].dist-q[].disb;

         ma=mb=;

         for(i=;i<=n;i++)

         {

             anss+=q[i].dist+q[i].dist;

             z=q[i].dist-q[i].disa;

             if(ax<z)

             {

                 ay=max(ax,ay);

                 ax=z;

                 ma=i;

             }

             else ay=max(ay,z);

             z=q[i].dist-q[i].disb;

             if(bx<z)

             {

                 by=max(bx,by);

                 bx=z;

                 mb=i;

             }

             else by=max(by,z);

         }

         if(ma!=mb)z=ax+bx;

         else z=max(ax+by,bx+ay);

         z=max(z,ax);

         z=max(z,bx);

         printf("%.12lf\n",anss-z);

     }

     return ;

 }

 /*

 //

 //

 */

相关文章