Problem F
Triangles
Alice has once again devised a game for Bob. She would first scatter seeds all over the kitchen floor. Then, Bob will have to kneel down and trace out triangles with his finger.
For each triangle Bob traces out, Alice gives him a number of cookies equal to the square of the area of the triangle. So if Bob traces out a triangle with vertices $(0,0)$, $(0,1)$ and $(1,0)$, Alice would give him $(\frac{1}{2})^2 = \frac{1}{4}$ cookies. Note that the number of cookies Alice gives Bob may not be a whole number. Bob is very excited because he loves cookies.
Unfortunately, Bob cannot just trace out any triangle he wants. At each round, he must choose three of the seeds to form the vertices of his triangle. Of course, the triangle he chooses cannot be degenerate (have area $0$). Furthermore, while he can reuse seeds from previous rounds, he cannot choose the same set of three seeds as he did in any of the previous rounds.
Alice likes watching Bob scramble around the room tracing triangles. She is willing to keep the game going as long as Bob can keep finding new triangles to draw. How many cookies can Bob win?
Input
The input consists of:
-
one line with one integer $N$ ($1 \leq N \leq 1\, 000\, 000$), the number of seeds;
-
$N$ lines each with two integers $x$ and $y$ ($0 \leq x,y < 1\, 000\, 000$), the coordinates of each seed.
It is possible for multiple seeds to share the same coordinates.
Output
Output one line with a single integer: the maximum number of cookies that Bob can win, assuming that there are an infinite number of rounds. Round your answer to four decimal places.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 0 0 0 1 1 0 1 1 |
1.0000 |
