TopCoder

Thumb 1800
weyryafjnm;
ちょっと天井見てくるわ。。。

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

83.8% (31/37)

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

// Sample input 1
6
0 0
0 1
0 2
1 0
1 1
1 2

// 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

Sample Output

// Sample output 1
3

// 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2 3 4
1 2000 524288 65536 1 2 3 4
2 2000 524288 65536 2 3 4
3 2000 524288 65536 2 3 4
4 2000 524288 65536 2 3 4
5 2000 524288 65536 2 3 4
6 2000 524288 65536 2 3 4
7 2000 524288 65536 2 3 4
8 2000 524288 65536 2 3 4
9 2000 524288 65536 2 3 4
10 2000 524288 65536 2 3 4
11 2000 524288 65536 2 3 4
12 2000 524288 65536 2 3 4
13 2000 524288 65536 3 4
14 2000 524288 65536 3 4
15 2000 524288 65536 3 4
16 2000 524288 65536 3 4
17 2000 524288 65536 3 4
18 2000 524288 65536 3 4
19 2000 524288 65536 3 4
20 2000 524288 65536 3 4
21 2000 524288 65536 3 4
22 2000 524288 65536 3 4
23 2000 524288 65536 3 4
24 2000 524288 65536 3 4
25 2000 524288 65536 4
26 2000 524288 65536 4
27 2000 524288 65536 4
28 2000 524288 65536 4
29 2000 524288 65536 4
30 2000 524288 65536 4
31 2000 524288 65536 4
32 2000 524288 65536 4
33 2000 524288 65536 4
34 2000 524288 65536 4
35 2000 524288 65536 4