编程之美初赛第一场 题目3 : 活动中心（答案）

描述
A市是一个高度规划的城市，但是科技高端发达的地方，居民们也不能忘记运动和锻炼，因此城市规划局在设计A市的时候也要考虑为居民们建造一个活动中心，方便居住在A市的居民们能随时开展运动，锻炼强健的身心。

城市规划局希望活动中心的位置满足以下条件：

1. 到所有居住地的总距离最小。

2. 为了方便活动中心的资源补给和其他器材的维护，活动中心必须建设在A市的主干道上。



为了简化问题，我们将A市摆在二维平面上，城市的主干道看作直角坐标系平的X轴，城市中所有的居住地都可以看成二维平面上的一个点。

现在，A市的城市规划局希望知道活动中心建在哪儿最好。



输入
第一行包括一个数T，表示数据的组数。

接下来包含T组数据，每组数据的第一行包括一个整数N，表示A市共有N处居住地

接下来N行表示每处居住地的坐标。



输出
对于每组数据，输出一行“Case X: Y”，其中X表示每组数据的编号(从1开始)，Y表示活动中心的最优建造位置。我们建议你的输出保留Y到小数点后6位或以上，任何与标准答案的绝对误差或者相对误差在10-6以内的结果都将被视为正确。



数据范围
小数据：1 ≤ T ≤ 1000, 1 ≤ N ≤ 10

大数据：1 ≤ T ≤ 10, 1 ≤ N ≤ 105

对于所有数据，坐标值都是整数且绝对值都不超过106





样例解释
样例1：活动中心的最优建造位置为(1.678787, 0)





样例输入
1
3
1 1
2 2
3 3
样例输出

Case 1: 1.678787

解题思路：

把距离问题求导，变成求导数为0的点的X值

代码：

//source here
#include <stdio.h>
  #include <stdlib.h>
  #include <math.h>
  typedef struct pointTag{
          int x;
          int y;
  }Point,*pPoint;
  int jisuan(pPoint p,int pN,float x)
  {
   int i;
   float result=0.0;
   for(i=0;i<pN;i++)
   {
    result+=(x-p[i].x)/sqrt((x-p[i].x)*(x-p[i].x)+p[i].y*p[i].y);
   }
   if(result<0)
   return -1;
   else return 1;
  }
  float AS(pPoint p,int pN)
  {float a,b,x;
         int i;
         a=(float)p[0].x;
         b=(float)p[pN-1].x;
         for(i=0;i<pN;i++) 
      //   printf("---%d %d\n\n",p[i].x,p[i].y);
       //  printf("%f %f",a,b);
         x=(float)(a+b)/2.0;
   while((b-a)>0.000001)
   {
    i=jisuan(p,pN,x);
    if(i==-1)
    {//???
    a=x;
    }else
    {//???
     b=x;
    }
    x=(a+b)/2.0;
    
    //printf("%f %f\n",a,b);
   }
   return (a+b)/2.0;
  }
  int main()
  {
      int tT,T;
      int i;
      int pN,tpN;
      double result;
      pPoint p;
      scanf("%d",&T);
      tT=T;
     
      while(T--)
      {
       scanf("%d",&pN);
       tpN=pN;
       p=(pPoint)malloc(sizeof(Point)*pN);
       i=0;
       while(tpN--)
       {
              scanf("%d %d",&(p[i].x),&(p[i].y));
              i++;
                   
       }
       //????
        result=AS(p,pN);
        printf("case %d: %f\n",tT-T,result);
        free(p);      
      }
   
  }