1 /* 2     题意：求费马点 3     三分：对x轴和y轴求极值，使到每个点的距离和最小 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          9 10 const int MAXN = 1e2 + 10;11 const int INF = 0x3f3f3f3f;12 double x[MAXN], y[MAXN];13 int n;14 15 double sum(double x1, double y1)    {16     double res = 0;17     for (int i=1; i<=n; ++i)    {18         res += sqrt ((x1 - x[i]) * (x1 - x[i]) + (y1 - y[i]) * (y1 - y[i]));19     }20     return res;21 }22 23 double cal(double x1)   {24     int l = 0.0, r = 10000.0;25     for (int i=1; i<=100; ++i)  {26         double lmid = (l + r) / 2;27         double rmid = (lmid + r) / 2;28         if (sum (x1, lmid) < sum (x1, rmid))    r = rmid;29         else    l = lmid;30     }31     return sum (x1, l);32 }33 34 int main(void)  {       //POJ 2420 A Star not a Tree?35     //freopen ("POJ_2420.in", "r", stdin);36 37     while (scanf ("%d", &n) == 1)   {38         for (int i=1; i<=n; ++i)    {39             scanf ("%lf%lf", &x[i], &y[i]);40         }41 42         double l = 0.0, r = 10000.0;43         for (int i=1; i<=100; ++i)  {44             double lmid = (l + r) / 2;45             double rmid = (lmid + r) / 2;46             if (cal (lmid) < cal (rmid))    r = rmid;47             else    l = lmid;48         }49         printf ("%.0f\n", cal (l));50     }51 52     return 0;53 }