Hide

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

Please log in to submit a solution to this problem

Log in