2015
02-21

Hyperspace Travel

Traveling through hyperspace is a risky thing, considering the fact that there are many stars, asteroids, (and possibly black holes!) out in the galaxy, and without careful planning, it’s so easy to end up thousands of light-years from your planned destination. Therefore people who don’t like uncertainty tend to avoid hyperspace traveling. However, as we need to travel through an unknown sector to attend the ACM/ICPC world final in the year 3007, and you’re the most experienced navigator and programmer we can find, it is unfortunately your responsibility to plan a journey that will lead us across the sector.

It is know that there are several strange asteroids in the sector �C every one of them is generating gravity anomaly in a circular area with a fixed radius around the asteroid. One particular position’s abnormality value is equal to the number of asteroids affecting that position.

You decided that you will follow one simple rule during your travel �C that is, you will always fly your ship along the gravity range boundary of one or more asteroids. Nevertheless, the possibility of failure remains due to the unpredictable nature of gravity anomaly, therefore you also want to minimize the absolute difference between the maximum abnormality value and the minimum abnormality value on your flight path. For simplicity, you can assume that all asteroids (as well as your flight path) will be on the plane Z = 0. Can you find the minimum absolute value with the help of your computer?

There are multiple test cases in the input file. Each test case starts with one integer N (2 <= N <= 30), the number of asteroids in the sector, followed by four real numbers, Sx, Sy, Tx, Ty, representing the x-coordinate and y-coordinate of your current position and your destination. Each of the following N lines consists of three real numbers X, Y and R (R >= 1), indicating that there is an asteroid at position (X, Y) with gravity range R.

There is a blank line after each test case. N = 0 indicates the end of input file and should not be processed by your program.

It is guaranteed that the input data is always legal, i.e. both your starting position and your destination are on the boundary of one or more asteroids, no two asteroids will have the same position, every real number in the input file has at most three digits after the decimal point, and the absolute value of any real number does not exceed 10000.

There are multiple test cases in the input file. Each test case starts with one integer N (2 <= N <= 30), the number of asteroids in the sector, followed by four real numbers, Sx, Sy, Tx, Ty, representing the x-coordinate and y-coordinate of your current position and your destination. Each of the following N lines consists of three real numbers X, Y and R (R >= 1), indicating that there is an asteroid at position (X, Y) with gravity range R.

There is a blank line after each test case. N = 0 indicates the end of input file and should not be processed by your program.

It is guaranteed that the input data is always legal, i.e. both your starting position and your destination are on the boundary of one or more asteroids, no two asteroids will have the same position, every real number in the input file has at most three digits after the decimal point, and the absolute value of any real number does not exceed 10000.

2
-1.000 0.000 1.000 0.000
0.000 0.000 1.000
1.000 0.000 1.000

2
-1.000 0.000 5.000 0.000
-1.000 -1.000 1.000
4.000 0.000 1.000

0

Case 1: 1
Case 2: -1

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

3. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n

4. 约瑟夫也用说这么长……很成熟的一个问题了，分治的方法解起来o(n)就可以了，有兴趣可以看看具体数学的第一章，关于约瑟夫问题推导出了一系列的结论，很漂亮