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 −10^{4} and 10^{4}
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