Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Necklace
Description There are y) is coordinates of a point number _{i}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**−**x**)_{i}^{2}+ (**y**−**y**)_{i}^{2}≤**r**_{i}^{2}, where**r**≥ 0._{i} - 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. Input The first line of the input contains one integer number y (1 000 ≤ _{i}x, _{i}y ≤ 1 000), separated by one space. It is guaranteed that at least one necklace exists._{i}Output The output has to contain r < 10 000). To avoid potential accuracy problems, a checking program uses the following rules._{i}- Figures #
**i**and #**j**definitely do not intersect if (**r**+_{i}**r**) ≤_{j}**d**− 10_{ij}^{−5} - Figures #
**i**and #**j**definitely intersect if (**d**+ 10_{ij}^{−5}) ≤ (ri + rj). - The case when
**d**− 10_{ij}^{−5}< (**r**+_{i}**r**) <_{j}**d**+ 10_{ij}^{−5}is decided in favour of a contestant. **d**equals_{ij}**sqrt((x**in the rules above._{i}− x_{j})^{2}+ (y_{i}− y_{j})^{2})
Sample Input 4 0 0 10 0 10 10 0 10 Sample Output 7 7 7 7 Source Northeastern Europe 2004, Western Subregion |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator