This page is still under construction.

Parts of this page are still being built. What you see may change.

Museum wall construction

Time limit1sMemory limit256 MB

Summary
Find the shortest closed curve enclosing N disjoint equal circles of radius R.
Level

Medium5 of 10

Topics
Geometry, Sorting
Solved
No attempts yet

Problem

Hongjun is extremely rich, and one day he takes an interest in art. He decides to build a museum with his money.

The floor of the museum is flat. For aesthetic reasons he stands NN cylindrical pillars on the floor, each perpendicular to it, and every pillar has the same radius RR. The outer wall is made of glass so thin that its thickness is ignored, and it also stands perpendicular to the floor, so seen from above the wall is a single closed curve.

The wall must enclose every pillar. Hongjun wants the wall that uses the least glass. Compute the length of that wall.

Input

The first line contains two natural numbers NN and RR separated by a space (2≤N≤1 0002 \le N \le 1\,000, 1≤R≤1001 \le R \le 100). NN is the number of pillars and RR is the radius shared by all of them.

Each of the next NN lines contains two integers xx and yy separated by a space, the coordinates of one pillar center when the floor is viewed as the xyxy plane (−104≤x,y≤104-10^4 \le x, y \le 10^4). No two pillars overlap or touch.

Output

Print the minimum length of a wall that encloses every pillar, rounded to six digits after the decimal point, on one line.

Examples2

  1. Example 1

    Input
    4 1
    -2 -2
    -2 2
    2 2
    2 -2
    
    Expected output
    22.283185
    
  2. Example 2

    Input
    2 5
    0 0
    0 20
    
    Expected output
    71.415927