Maximum perimeter P57181


Statement
 

pdf   zip

html

Given n different points on the plane, pick any three of them so that the perimeter of the resulting triangle is maximum.

Input

Input consists of several cases, each with n followed by n pairs of integer coordinates (x, y). Assume 3 ≤ n ≤ 104, −108x, y ≤ 108, and that no three given points are colinear.

Output

For every case, print the maximum perimeter of all the possible triangles with four digits after the decimal point. The input cases have no precision issues.

Observation

All “big” private test cases were built by choosing a “typical” geometric figure (such as a rectangle, a triangle, a circle, an ellipse, or alike), and placing n points at random inside it, always avoiding repeated points and points that would be collinear with two other points.

Public test cases
  • Input

    3  0 0  0 1  1 0
    5  -1 1  3 2  1 1  -2 -1  1 -3
    

    Output

    3.4142
    14.8217
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Novè Concurs de Programació de la UPC - Final
    Date
    2011-09-21