2015
04-13

# X Property

The X property is a property of two intersected circles. Suppose we have two intersected circls P and Q, and they intersect at A and B. If the two circles satisfy:

AP*BQ+AQ*BP=AB*PQ

we call these two circles satisfy the X property.

Given N circles on a plane, can you find a circle which has X property with all the N given circles?

The first line comes an integer T (T<=20), indicating there are T test cases. For each case, there will be an integer N (1<=N<=100000) in the first line. Then comes N lines. Each of them contains three integer numbers Xi, Yi, Ri (-1000000<=Xi, Yi<=1000000, 0<Ri<=1000000) representing the center of the ith circle and the radius of it.

The first line comes an integer T (T<=20), indicating there are T test cases. For each case, there will be an integer N (1<=N<=100000) in the first line. Then comes N lines. Each of them contains three integer numbers Xi, Yi, Ri (-1000000<=Xi, Yi<=1000000, 0<Ri<=1000000) representing the center of the ith circle and the radius of it.

3
3
0 0 1
2 0 1
1 3 1
2
0 0 1
1 1 2
3
0 1 1
0 -1 1
-1 0 1

1.000000 1.333333 1.333333
-2
-1

1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

3. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。