Score : 600 points
There are N dots in a two-dimensional plane. The coordinates of the i-th dot are (x_i, y_i).
We will repeat the following operation as long as possible:
We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.
Input is given from Standard Input in the following format:
N x_1 y_1 : x_N y_N
Print the maximum number of times we can do the operation.
3 1 1 5 1 5 5
1
By choosing a = 1, b = 1, c = 5, d = 5, we can add a dot at (1, 5). We cannot do the operation any more, so the maximum number of operations is 1.
2 10 10 20 20
0
There are only two dots, so we cannot do the operation at all.
9 1 1 2 1 3 1 4 1 5 1 1 2 1 3 1 4 1 5
16
We can do the operation for all choices of the form a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5), and no more. Thus, the maximum number of operations is 16.