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?

Input

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.

Output

Output 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.

Sample Input

8 1
1 4
3 2
7 9
5 4
9 5
6 7
9 1
11 8

Sample Output

34.408

Diagram

All Submissions
Best Solutions

Point Value: 20
Time Limit: 1.00s
Memory Limit: 32M
Added: May 10, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...