珠海邀请赛个人解题报告 Problem B: Magic Matrix

  Problem B: Magic Matrix

 Description
A new term of Hogwarts Magic School is coming, while the most powerful black
magician Voldemort is also going to come back. In order to resist Voldemort and save the  magic  world,  Hogwarts  Magic  School  has  to  practice  white  magic  diligently.
Hogwarts’ principal Dumbledore and Harry Potter plan  to  set up a magic matrix  to resist the attacks from Voldemort.
N magicians stand  in n  fixed positions. Each of  them concentrates  their magic power to cover a circle of a certain radius. A magician can move inside his/her circle.
If the i-th magician and the (i%n+1)-th magician are at the same place they can give their magic power to each other. However, there is a restriction that the i-th magician’s circle can NOT overlap with (i%n+1)-th magicians’, otherwise the whole magic matrix will be unstable. When Voldemort comes, all magicians must concentrate their magic power and transmit it to Harry Potter. Now the question comes. Can they succeed in setting up the magic matrix? If so, output the radius of each magician’s power circle, and NONE  if  impossible. There may be several solutions, so you must maximal  the circle of Harry Potter, the reading role of the whole story, who's the first magician.
Input
The input has multiple test cases. For each test case: The first line is an integer n (n<=1000), the number of magicians. Each of next n lines contains two real numbers, giving the coordinate of the each magician.
Output
If it is impossible, just output NONE.
If  it  is  possible,  you  should  output  n  lines.  Each  line  contains  a  number
representing the radius of a magician. Two digits after the decimal point are required.

Sample Input
3
0 0
3 0
3 4

Sample Output
2.00
1.00
3.00
 
Hint
Radius 0 is possible.

 

这道题当没仔细看的时候，以为是一道很难的题，然而仔细读完，就发现它只是一道求解非齐次线性方程组的题目。

大概意思是，输入给了N个人的坐标，然后他们各自以自己为圆心发动范围魔法，当每个人发动的魔法区域（一个圆形区域）互相相切时候，可以发挥出魔法的最大威力。依次求出每个人的魔法半径。

设魔法师依次为 A[1...N] ，那么先按顺序算出相邻两个人的距离
建立起方程组：

A1 + A2 = Dis[1][2]
A2 + A3 = Dis[2][3]
        .
        .
        .             
Ai  +  Aj =  Dis[i][j]

如果方程组有解，求解出方程组的解即可，否则输出NONE;
另外，这道题的Memory Limit 是 8192K，用高斯消元来解会爆空间。不过这个方程组每行只有两个未知数，所以可以推出公式来求解

例如：

    r1 + r2 = d1
    r2 + r3 = d2
    r3 + r1 = d3
 则：r1 = d1 - r2 = d1 - (d2 - r3) = d1 - (d2 - (d3 - r1))
 化简得: r1 = (d1 - d2 + d3) / 2
 用数学归纳法可以证明出通式。

贴出我的代码:(^ ^ 排第一的代码）

 

#include<stdio.h>#include<math.h>struct coor{double x,y;}point_head,point_pre,point_now;double d(coor a,coor b) { return sqrt((a.x-b.x) * (a.x-b.x) + (a.y - b.y) * (a.y - b.y));}int main(){ int N; double dis[1000]; while(scanf("%d",&N)!=EOF) { for(int i = 0; i < N; i++) { scanf("%lf%lf",&point_now.x,&point_now.y); if( i == 0 ) point_pre = point_head = point_now; else { dis[i-1] = d(point_now,point_pre); point_pre = point_now; } if( i == N-1 ) dis[i] = d(point_now,point_head); } bool flag = true; double solv,high = 0, low= dis[0] < dis[N-1] ? dis[0] : dis[N-1] , r=dis[0]; for(int i = 1; i<N ;++i) { r+= ( (i % 2) ? -1 : 1 ) * dis[i]; if( i % 2 && high < r)high=r; else if( i % 2 == 0 && low>r) low=r; if(high > low || low < 0) {flag=false; break;} } solv = (N%2) ? (r / 2) : low; if(flag) { printf("%.2lf/n",solv); for(int i = 0; i < N-1;++i) { solv=dis[i]-solv; printf("%.2lf/n",solv); } }else printf("NONE/n"); } return 0;}