русский
english
0214. Mad Skaters
| Input file name: | d.in |
| Output file name: | d.out |
| Time limit: | 2 s |
| Memory limit: | 64 megabytes |
Did you hear of the new kind of sport, the ⌠Mad Skating■? You probably didn▓t. I didn▓t either┘ But anyway here is the problem to solve. Mad Skating involves riding along the border of the skating field. The ice is very slippery so if some skater crashes he will drift towards the closest wall or corner (whichever comes first) with enormous speed and probably will never skate again due to an awful trauma on impact. There are positions at which referees must be placed and referees must see every point of the skating field border (where skaters ride). Skaters run along the border and if one of them slams, he must face no wall and he must face no a single corner during his drift, i.e. the field border should be perfectly smooth without any sharp corners and tangent to the border at any of its points must lead outside the field (otherwise a skater will inevitably blow a hole in the opposite wall). The drifting speed is unpredictable; a skater can make any number of rounds along field border until he finally stops (provided the field is correct, i.e. he fill not fly kilometers away from the field if smoothness restrictions are not met). Now let▓s come to some mathematical definition. Given a set of 2D points (referee positions); you are to find minimum non-zero perimeter of the field border which:
- Contains no sharp corners.
- Tangent to the border does not have any points within the area enclosed by the field border.
- Every point of the field border is visible from every of given points (referee positions).
Input file
The first line contains the only number N - the number of referee points, 0 ≤ N ≤ 65▓536. The following N lines contain coordinates of i▓th point in X Y format. Coordinates will be given with at most two digits after the decimal point and will not exceed 1000.00 by their absolute value.
Output file
Output minimal Mad Skating field perimeter or highest of lower limits for it (whatever you think is correct) with 2-digits precision. Consider that skaters have unnatural leaping ability allowing them to jump over each other and over referees, thus there will be no skater-to-skater or skater-to-referee collisions, even if they drift after slamming on the ice. However, a crashed skater cannot stand up and ride again until he stops, so please leave no sharp corners or dangerous walls. Please note that skaters can ride, and thus drift, in both directions. Referees do not move at all.
Example:
| d.in | d.out |
|---|---|
| 4 0 0 1.0 0.0 1.00 1.00 0 1 | 4.00 |
Source: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Author: Denis Koshman
Discuss Submit a solution
Printable version