| Submit | All submissions | Best solutions | Back to list |
COLDIAM - Collect Diamonds |
Misty has won a contest in a jewellery store and now she is allowed to collect diamonds as prize. But the store manager doesn't wan't to be so generous. He has spread several diamonds on the floor and now he asks Misty to encircle them using her gold chain. After that she can exhange her chain with all the diamonds that are encircled. Misty can manage to get the gold chain of any length from her friends. But she has to minimise the length and also want to collect all the diamonds on the floor. Diamonds lying on the chain are also considered to be inside. Help her to find the minimum length of the gold chain required.
Input
First line of input consist of a single positive integer n <= 1000 i.e number of diamonds. Next n lines consist of two integers x,y that denotes position ( coordinates ) of diamonds on the floor. 0 =< x,y <= 1000
Output
Minimum length of gold chain required so that misty can collect all the diamonds. Answer should be rounded to two places after decimal.
Example
Input:
4
1 0
0 1
1 1
0 0
Output:
4.44
| Added by: | XeRoN!X |
| Date: | 2010-09-07 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS VB.NET |
hide comments
|
2016-07-08 02:24:30
@Simes: You have to determine the circumference of a circle which can contain all diamonds - in the example, the circle will have it's center at (0.5,0.5) with radius sqrt(2), giving it a circumference sqrt(2) * pi = 4.44288... = 4.44 |
|
|
2016-03-11 10:24:18 Simes
@lort9119: Thanks, but I'm afraid that doesn't help me very much - a convex hull would encircle all diamonds. |
|
|
2015-11-22 12:58:19
Simes : The diamonds need to be encircled! |
|
|
2015-10-28 12:20:52 Simes
How is the output for the example 4.44? Isn't this asking for a convex hull, and so the answer should be 4.00? What am I missing? |
RSS