NECKLACE - Necklace
There are N points marked on a surface, pair (xi, yi) is coordinates of a point number i. Let's call a necklace a set of N figures which fulfills the following rules.
- The figure #i consists of all such points (x, y) that (x - xi)2 + (y - yi)2 ≤ ri2, where ri ≥ 0.
- Figures #i and #(i+1) intersect (1 ≤ i < N).
- Figures #1 and #N intersect.
- All the rest pairs of figures do not intersect.
Write a program which takes points and constructs a necklace.
First line of input contains an integer t (1 ≤ t ≤ 45), equals to the number of testcases. Then descriptions of t testcases follow.
The first line of the description contains one integer number N (2 ≤ N ≤ 100). Each of the next N lines contains two real numbers xi, yi (-1000 ≤ xi, yi ≤ 1000), separated by one space. It is guaranteed that at least one necklace exists for each testcase.
For each testcase your program should output exactly N lines. A line #i should contain real number ri (0 ≤ ri < 10000). To avoid potential accuracy problems, a checking program uses the following rules.
- Figures #i and #j definitely do not intersect if ri + rj ≤ dij - 10-5.
- Figures #i and #j definitely intersect if dij + 10-5 ≤ ri + rj.
- The case when dij - 10-5 < ri + rj < dij + 10-5 is decided in favour of a contestant.
- dij equals sqrt((xi - xj)2 + (yi - yj)2) in the rules above.
Input: 1 4 0 0 10 0 10 10 0 10 Output: 7 7 7 7
I have solved this problem by simplex algorithm,but it is too slow and got TLE on poj,how to solve it faster?