折线中点

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

给定平面上N个点P1, P2, ... PN，将他们按顺序连起来，形成一条折线。 请你求出这条折线的中点坐标。

Input:

第一行包含一个整数N。 (2 <= N <= 100) 下面N行每行包含两个整数Xi, Yi代表Pi的坐标。(0 <= Xi, Yi <= 10000)

Output:

输出折线段的中点坐标。坐标保留一位小数。（中点坐标：在此折线上取一个点，使折线左右两边的长度相等）

Sample Input:

3  0 0   30 30  40 20

Sample Output:

20.0 20.0 解题思路：纯数学题，思路比较简单。数组c保存的是当前点到前一个点的距离，通过累计，当求和完折线总长度时，应该找折线总长一半所在的线段。设p(x,y)是折线的中点，A(a1,b1)是p的前一个点，B(a2,b2)是p的后一个点，线段AP：线段AB=t，则求中点p坐标应为：x=a1+t*(a2-a1);y=b1+t*(b2-b1)。 AC代码：

1 #include 
      
        2 using namespace std; 3 int main() 4 { 5     int N; 6     int k,a[105],b[105]; 7     double sum,p1,p2,tmp,c[105],p; 8     while(cin>>N){ 9         memset(c,0,sizeof(c));10         cin>>a[0]>>b[0];11         k=c[0]=sum=0;12         for(int i=1;i
       
        >a[i]>>b[i];14             sum+=sqrt((a[i]-a[i-1])*(a[i]-a[i-1])+(b[i]-b[i-1])*(b[i]-b[i-1]));15             c[i]=sum;16         }17         tmp=sum/2.0;18         for(int i=0;i
        
         =tmp){20                 k=i;21                 break;22             }23         }24         //k=lower_bound(c,c+N,tmp)-c;25         tmp-=c[k-1];26         p=tmp/(c[k]-c[k-1]);27         p1=a[k-1]+(a[k]-a[k-1])*p;28         p2=b[k-1]+(b[k]-b[k-1])*p;29         printf("%.1f %.1f\n",p1,p2);30     }31     return 0;32 }