2221 . 足球場
TopCoder
Tags
Description
不知道為什麼，附中忽然獲得了一塊超大的土地，而且學校居然不打算在那裡蓋校舍，而是打算建造新的足球場。
這塊新的土地可以被視為一個邊長是 $10^ 9$ 微米（1 微米是 $10^ {-6}$ 公尺）的正方形，西南角的座標是 $(0,0)$、東南角的座標是 $(10^ 9,0)$、西北角的座標是 $(0,10^ 9)$、東北角的座標是 $(10^ 9,10^ 9)$，如下圖。
因為這塊土地很大，學校只想選擇一個矩形區域作為足球場，而且學校並不在乎這個足球場的邊長是否符合標準，只要是面積為正的矩形即可，無論多大多小、長寬比例為何都沒有關係，這個矩形的邊也不一定要和土地的邊平行或垂直。
為了在最好的地方建造足球場，學校請來了一個風水師，他說：「足球場的四個角落位置可不能亂選啊，在這塊土地上，只有 $N$ 個點能作為足球場的頂點，其中第 $i$ 個點的座標是 $(x_i,y_i)$，四個頂點必須從這些點中選擇才行。」
總務處想要知道有幾個不同的矩形區域可以作為足球場。
測資限制
- $1 \leq N \leq 1000$
- $0 \leq x_i,y_i \leq 10^ 9$
Input Format
第一行有一個整數 $N$，表示風水師提供的點的數量。
接下來有 $N$ 行，其中第 $i$ 行有兩個整數 $x_i,y_i$，表示第 $i$ 個點的座標。
Output Format
輸出一個整數，表示有幾個不同的矩形區域可以作為足球場。
Sample Input 1
6
0 0
0 1
0 2
1 0
1 1
1 2
0 0
0 1
0 2
1 0
1 1
1 2
Sample Output 1
3
Sample Input 2
19
4 2
6 4
4 6
2 12
4 18
8 10
12 2
8 20
10 16
12 12
14 8
18 4
12 22
16 14
20 6
20 12
20 18
18 20
20 22
4 2
6 4
4 6
2 12
4 18
8 10
12 2
8 20
10 16
12 12
14 8
18 4
12 22
16 14
20 6
20 12
20 18
18 20
20 22
Sample Output 2
19
Hints
對於第一筆範測，以下是 3 組能作為矩形區域的四個頂點的點編號：
- $\{1,4,2,5\}$
- $\{1,4,3,6\}$
- $\{2,5,3,6\}$
Problem Source
2021 師大附中校隊培訓 模擬競賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~12 | $N \le 80$ | 12 |
| 3 | 0~24 | $N \le 200$ | 23 |
| 4 | 0~35 | 無額外限制 | 65 |