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 – 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 – 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, S_x, S_y, T_x, T_y, 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.

For each test case, output one integer on one separate line as requested. If there is no way for you to reach the destination by only flying along asteroids’ gravity range boundaries, output -1 instead.

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

2010 Asia Tianjin Regional Contest