Mine Sweeper
Национална Олимпиада по Информатика 2009, Кръг 3
Time Limit: 0.2s, Memory Limit: 64MiB
Като всяка модерна ученичка, Ели се занимава с най-различни извънкласни дейности – театрално изкуство, скално катерене, клуб по дебати, сапьорство. Последното навярно би учудило доста от вас, но работата е интересна и не толкова сложна.

Mines Example Като начинаещ сапьор, на Ели й възлагат единствено да открие къде лежат мините в някое минно поле и да ги огради с маркировъчна лента (съответно да предпази случайни минувачи). Елеонора, от друга страна, няма проблем със самото откриване на мините – нейният най-нов модел смартфон (малко обидно за изобретението, което тя притежава) с вградена 42 мегапикселова камера, безжичен интернет, GPS, и металодетектор правят работата приятна и забавна.

След като е направила снимка на минното поле, тя трябва да огради всички мини с едно единствено парче маркировъчна лента, като се стреми дължината на тази лента да е минимална. Всяка мина представлява кръг с радиус R и координати (Xi, Yi). Ели Ви е показала картата на минното поле и се чуди лента с каква дължина да вземе. Можете ли да й помогнете с това?
Вход
На първия ред на стандартния вход ще бъдат въведени две цели числа N и R – съответно броят мини и радиусът на всяка от тях. На следващите N реда ще бъдат дадени координатите Xi и Yi на всяка мина. Мините могат да се застъпват (с цел експлозията им да е по-силна).
Изход
На стандартния изход изпечатайте едно единствено число с плаваща запетая – дължината на най-късата лента, с която могат да се оградят всички мини. Отговорът ще бъде зачетен за верен при абсолютна или релативна разлика, по-малка от 10-9.
Ограничения
  • 1 ≤ N ≤ 100,000
  • 1 ≤ R ≤ 100
  • -20,000 ≤ Xi, Yi ≤ 20,000
Примерен Вход Примерен Изход
8 1 1 4 3 2 7 9 5 4 9 5 6 7 9 1 11 8 34.407840153029
Точките от показаната картинка.
Мрън!