Five Points

Time limit2sMemory limit512 MB

Summary

Given up to 5 distinct points, each gets a half-line in a uniformly random direction. Find the probability that no two half-lines share a point.

Level: Medium7 of 10
Topics: Geometry, Probability
Solved: No attempts yet

Problem

You have placed $n$ distinct points on a plane. Then you will draw a half-line starting from each point in a direction chosen uniformly at random and independently from other points. Find the probability that no two half-lines will intersect.

Input

The first line of the input contains a single integer $n$ ( $2 \le n \le 5$ ), denoting the number of points.

The $i$ -th of the following $n$ lines contains two integers $x_i$ and $y_i$ ( $-100 \le x_i, y_i \le 100$ ), denoting the coordinates of the $i$ -th point.

No two points coincide.

Output

Display the probability that no two half-lines will have a common point. Your answer must be correct to within an absolute or relative error of $10^{-9}$ .

Examples2

Example 1
Input
```
2
0 0
1 1
```
Expected output
```
0.7500000000000
```
Example 2
Input
```
3
7 8
7 7
8 8
```
Expected output
```
0.4303385416667
```