Closest pair P70827


Statement
 

pdf   zip

html

Given several points on the plane, compute the Euclidean distance between the closest pair.

Input

Input consists of the coordinates of n different points. The coordinates are real numbers with absolute value at most 105. Assume 2 ≤ n ≤ 105.

Output

Print the smallest distance between all pairs of points, with five digits after the decimal point. The input cases have no precision issues.

Public test cases
  • Input

    1.2 4.5
    2.4 1.2
    3.3 1.1
    4.4 4.4
    7.7 1.1
    1.1 2.1
    8.6 1.9
    3.3 9.0
    

    Output

    0.90554
    
  • Input

    1 1
    2 2
    3 3
    4 4
    5 5
    

    Output

    1.41421
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Semifinal
    Date
    2012-06-30