2009 Bulgarian Olympiad in Informatics
Task 1: Minesweeper
There is a dangerous minefield somewhere in Bulgaria. You have been assigned to enclose them all with a "warning band" so that future travellers are aware of the danger.
After searching around with a metal detector, you have located all of the mines. Each mine is a perfectly round shape with radius R at location x, y. Can you write a program to determine the length of the shortest band that will enclose all of the mines?
On the first line of the standard input two integers N and R will be given - the number of the mines and their radius. On the next N the coordinates x and y of the center of a mine will be given. The mines will overlap (in order to create a more powerful blast, for example)
N will be between 1 and 10,000, inclusive, and x,y will be between -20,000 and 20,000.
OutputOutput a single line, containing the minimal length of a band.
Your answer will be considered correct if it is within 0.001 of the answer.
8 1 1 4 3 2 7 9 5 4 9 5 6 7 9 1 11 8
Point Value: 20
Time Limit: 1.00s
Memory Limit: 32M
Added: May 10, 2009
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3