首页 > ACM题库 > HDU-杭电 > hdu 3878 X Property待解决[解题报告]C++
2015
04-13

hdu 3878 X Property待解决[解题报告]C++

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选项是不对的。