Description

Xiao Tu (pinyin: Xiao Tu) likes running on the track at night. After finishing two laps today, he started the following game.

The track is a convex $n$-gon whose $n$ vertices are numbered in counterclockwise order from $0$ to $n - 1$. Now Xiao Tu stands uniformly at random at some point inside the track, denoted as point $p$. Connect point $p$ to all $n$ vertices to form $n$ triangles (i.e., triangles $(p, i, i + 1)$ for all $i$, with indices modulo $n$). If the triangle formed by $p$, vertex $0$, and vertex $1$ has the smallest area among these $n$ triangles, Xiao Tu considers this a correct placement.

Now Xiao Tu wants to know the probability that a single placement is correct.

Input Format

The first line contains an integer $n$, the number of vertices of the track.

The next $n$ lines each contain two integers $x_i, y_i$, the coordinates of the vertices.

The input guarantees that the vertices are given in counterclockwise order, they form a convex polygon, and no three points are collinear.

Output Format

Output a single number: the probability of a correct placement, rounded to $4$ decimal places.

5
1 8
0 7
0 0
8 0
8 8

0.6316

Hint

For $30\%$ of the testdata, $3 \le n \le 4$, $0 \le x, y \le 10$.

For $100\%$ of the testdata, $3 \le n \le 10^5$, $-10^9 \le x, y \le 10^9$.

Translated by ChatGPT 5