2234 . 2D Chess Without Multiverse Time Travel

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

90.9% (40/44)

Submission's AC Ratio

39.3% (55/140)

Tags

pre-nhspc-2021 全國模擬賽

Description

小崴最近迷上了新遊戲「 5D 西洋棋多宇宙時空穿梭（ 5D Chess With Multiverse Time Travel ）」。但在⼀段時間的研究後，小崴發現了這個遊戲的必勝⽅法，⾃此戰無不勝，也讓小崴對這款遊戲感到厭倦。因此，他修改了規則並發明了新遊戲「 2D 西洋棋無多宇宙時空穿梭（ 2D Chess Without Multiverse Time Travel ）」。

在這個遊戲裡，棋盤是⼀個無限⼤的平⾯，上⾯只有皇后⼀種棋⼦。現在給定棋盤上所有皇后的位置，請輸出有多少對皇后可以互相攻擊。

註：皇后每次移動可以⾃⼋個⽅位中擇⼀並向該⽅位移動任意距離，但不可越過其他皇后。若該皇后停在了有另⼀個皇后的格⼦中，則該皇后會吃掉另⼀個皇后。若 A、B 兩皇后滿⾜ A 能在⼀步以內吃掉 B；B 也能在⼀步以內吃掉 A ，則稱這對皇后可以互相攻擊。

Input Format

輸⼊的第⼀⾏包含⼀個正整數 N ，表⽰棋盤上皇后的數量。

接著有 N ⾏，第 i ⾏有兩個以空⽩分隔的整數 xi 、yi ，表⽰第 i 個皇后的座標。

保證不存在任兩個皇后的座標相同。

對於所有的測資，保證：

  • 1≤N≤106。
  • |xi|,|yi|≤109。
  • 對於所有 i≠j ，都有 (xi,yi)≠(xj,yj) 。

Output Format

請輸出⼀個整數，代表有多少對皇后可以互相攻擊。

Sample Input 1

4
0 0
1 1
0 1
-1 -1

Sample Output 1

4

Sample Input 2

4
-5 5
5 5
5 -5
-5 -5

Sample Output 2

6

Hints

Problem Source

110 學年度普通型⾼級中等學校資訊學科能⼒競賽決賽 模擬賽

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~6 N<100,|xi|,|yi|<1000 34
3 0~23 N<105,|xi|,|yi|<109 31
4 0~38 N<106,|xi|,|yi|<109 35

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 3 4
8 2000 524288 65536 3 4
9 2000 524288 65536 3 4
10 2000 524288 65536 3 4
11 2000 524288 65536 3 4
12 2000 524288 65536 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 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
36 2000 524288 65536 4
37 2000 524288 65536 4
38 2000 524288 65536 4
Submit
Back to Top