Fish’s mission

Fish’s mission 也就是求一个坐标到各个食堂的距离和最小，随机化做应该也是可以的。标程用的方法是利用单调性，不断尝试四个方向，二分的方法做的。实际上就是蚁群退火算法。

 #include <cmath>

 #include <cstdio>

 #define pi acos(-1.0)

 struct Point{

     double x,y;

     Point(){}

     Point(double a,double b){

         x=a,y=b;

     }

 }point[];

 double pt_distance(const Point &p1,const Point &p2){

     return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));

 }

 double get_all_dis(const Point &p,int n){

     double ans=0.0;

     for (int i=; i<n; i++) ans+=pt_distance(point[i],p);

     return ans;

 }

 int main() {

     int n;

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

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

             scanf("%lf%lf",&point[i].x,&point[i].y);

         Point st=point[];

         double step=,mind=get_all_dis(st,n);

         while (step>0.0002){

             int ok=;

             while (ok){

                 Point tmp,nt;

                 double t;

                 ok=,nt=st;

                 tmp=Point(st.x,st.y+step);

                 t=get_all_dis(tmp,n);

                 if (t<mind) mind=t,ok=,nt=tmp;

                 tmp=Point(st.x,st.y-step);

                 t=get_all_dis(tmp,n);

                 if (t<mind) mind=t,ok=,nt=tmp;

                 tmp=Point(st.x+step,st.y);

                 t=get_all_dis(tmp,n);

                 if (t<mind) mind=t,ok=,nt=tmp;

                 tmp=Point(st.x-step,st.y);

                 t=get_all_dis(tmp,n);

                 if (t<mind) mind=t,ok=,nt=tmp;

                 st=nt;

             }

             step=step/2.0;

         }

         printf("%.3lf\n",mind);

     }

     return ;

 }