## NECKLACE - Necklace

no tags

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)2ri2, where ri0.
• Figures #i and #(i+1) intersect (1i < 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.

### Input

First line of input contains an integer t (1t45), equals to the number of testcases. Then descriptions of t testcases follow.

The first line of the description contains one integer number N (2N100). Each of the next N lines contains two real numbers xi, yi (-1000xi, yi1000), separated by one space. It is guaranteed that at least one necklace exists for each testcase.

### Output

For each testcase your program should output exactly N lines. A line #i should contain real number ri (0ri < 10000). To avoid potential accuracy problems, a checking program uses the following rules.

• Figures #i and #j definitely do not intersect if ri + rjdij - 10-5.
• Figures #i and #j definitely intersect if dij + 10-5ri + 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.

### Example

```Input:
1
4
0 0
10 0
10 10
0 10

Output:
7
7
7
7

``` yangshen: 2012-05-25 08:53:24 I have solved this problem by simplex algorithm,but it is too slow and got TLE on poj,how to solve it faster?