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.


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.


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.


0 0
10 0
10 10
0 10


hide comments
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?

Added by:Ivan Metelsky
Time limit:1.632s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:NEERC Western Subregion QF 2004