Never trust Ivan P47610


Statement
 

pdf   zip

html

You are given a convex polygon. What is the probability that choosing any three vertices, plus any point inside the polygon, the four points do not form a convex quadrilateral?

Input

Input consists of several cases. Every case begins with the number of points n, followed by n pairs of coordinates in clockwise or anticlockwise order. Assume 3 ≤ n ≤ 1000, and that the coordinates are real numbers between −104 and 104 with at most two digits after the decimal point.

Output

For every case, print the asked probability with four digits after the decimal point. The input cases have no precission issues.

Public test cases
  • Input

    3  2 0  3 1  4 0
    4  0 0  0 10  10 10  10 0
    5  7.2 -5.3  4.5 5.9  -1.2 6.3  -5.0 0  0 -8
    

    Output

    1.0000
    0.5000
    0.3609
    
  • Information
    Author
    Ivan Geffner
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Dotzè Concurs de Programació de la UPC - Final
    Date
    2014-10-01