2221 . 足球場

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

南ことり
ε=ε=ε=( ￣▽￣) 烙跑囉

User's AC Ratio

95.8% (23/24)

Submission's AC Ratio

86.8% (46/53)

Tags

hsnu-2021-thspc-mock

Description

不知道為什麼，附中忽然獲得了一塊超大的土地，而且學校居然不打算在那裡蓋校舍，而是打算建造新的足球場。

這塊新的土地可以被視為一個邊長是 109 微米（1 微米是 10−6 公尺）的正方形，西南角的座標是 (0,0)、東南角的座標是 (109,0)、西北角的座標是 (0,109)、東北角的座標是 (109,109)，如下圖。

土地

因為這塊土地很大，學校只想選擇一個矩形區域作為足球場，而且學校並不在乎這個足球場的邊長是否符合標準，只要是面積為正的矩形即可，無論多大多小、長寬比例為何都沒有關係，這個矩形的邊也不一定要和土地的邊平行或垂直。

為了在最好的地方建造足球場，學校請來了一個風水師，他說：「足球場的四個角落位置可不能亂選啊，在這塊土地上，只有 N 個點能作為足球場的頂點，其中第 i 個點的座標是 (xi,yi)，四個頂點必須從這些點中選擇才行。」

總務處想要知道有幾個不同的矩形區域可以作為足球場。

測資限制

  • 1≤N≤1000
  • 0≤xi,yi≤109

Input Format

第一行有一個整數 N，表示風水師提供的點的數量。

接下來有 N 行，其中第 i 行有兩個整數 xi,yi，表示第 i 個點的座標。

Output Format

輸出一個整數，表示有幾個不同的矩形區域可以作為足球場。

Sample Input 1

6
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

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≤80 12
3 0~24 N≤200 23
4 0~35 無額外限制 65

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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
Submit
Back to Top