Distance between polygons P27519


Statement
 

pdf   zip

html

That’s all: Compute the distance between the sides of two given polygons.

Input

Input consists of several cases. Each case begins with two numbers n and m. Follow the n points that define the first polygon, and the m points that define the second polygon. Assume 1 ≤ n, m ≤ 103. All the given coordinates are integer numbers with absolute value at most 104.

Output

For every case, print its number followed by the minimum distance between the sides of the two polygons, rounded to four digits after the decimal point. If handled correctly, the input cases have no precision issues.

Public test cases
  • Input

    3 3
    0 0  0 1  1 0
    2 2  1 2  2 1
    
    4 2
    0 0  6 6  0 6  6 0
    3 4  3 5
    
    1 3
    8 8
    8 7  8 9  8 9
    
    2 2
    -1 -1  1 1
    -1 1  1 -1
    
    1 1
    0 0
    0 0
    
    2 2
    0 0  0 2
    0 1  0 3
    
    1 1
    1 1
    1 0
    

    Output

    Case #1: 1.4142
    Case #2: 0.7071
    Case #3: 0.0000
    Case #4: 0.0000
    Case #5: 0.0000
    Case #6: 0.0000
    Case #7: 1.0000
    
  • Information
    Author
    Albert Graells
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Semifinal
    Date
    2011-06-29