Building Roads

시간 제한2초메모리 제한1024 MB

요약
N개의 점이 주어질 때 최소 신장 트리를 만들고, 두 점 사이 최단 거리 중 가장 긴 값인 지름을 최소화하여 출력한다.
난이도

어려움10점 중 8점

유형
최소 신장 트리, 그래프, 기하
정답자
아직 제출이 없습니다

문제

A multi-billionaire has a vision to build a completely new city from scratch. After much research and consultations, locations have been selected for all the houses, shopping malls, restaurants, etc. Roads now have to be added to ensure that every location is reachable by any other location, but only the minimum number of roads should be built. For environmental reasons, it is also desirable to minimize the longest travel between two locations. Each road must connect two locations, but roads may cross each other by adding overpasses (so traffic cannot switch to a different road between locations).

What is the minimum length in the longest travel in the road network designed?

입력

The first line of input contains an integer 2≤N≤2002 \leq N \leq 200 specifying the number of locations to follow. Each of the next NN lines contains two integers x_ix\_i and y_iy\_i (−5000≤x_i,y_i≤5000-5000 \leq x\_i, y\_i \leq 5000), specifying the coordinates of the iith location. All coordinates are specified in meters, and all locations are distinct.

출력

Output the minimum possible length (in meters) of the longest travel between two locations. Your answer should have a relative or absolute error of less than 10−310^{-3}.

예제2

  1. 예제 1

    입력
    3
    0 0
    10 0
    0 10
    
    예상 출력
    20.0000000000
    
  2. 예제 2

    입력
    9
    0 0
    10 0
    0 10
    -10 0
    0 -10
    10 10
    10 -10
    -10 10
    -10 -10
    
    예상 출력
    28.2842712475