TopCoder

Thumb screenshot from 2022 02 07 14 53 28
FHVirus
到底要用哪一種 Code style 呢?

User's AC Ratio

88.2% (15/17)

Submission's AC Ratio

61.5% (24/39)

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$ ⾏有兩個以空⽩分隔的整數 $x i$ 、$y i$ ,表⽰第 $i$ 個皇后的座標。

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

對於所有的測資,保證:

  • $1 \le N \le 10^ 6$。
  • $|x_i|, |y_i| \le 10^ 9$。
  • 對於所有 $i \neq j$ ,都有 $(x i , y i) \neq (x j , y j)$ 。

Output Format

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

Sample Input

// Sample input 1
4
0 0
1 1
0 1
-1 -1

// Sample input 2
4
-5 5
5 5
5 -5
-5 -5

Sample Output

// Sample output 1
4

// Sample output 2
6

Hints

Problem Source

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

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資。 0
2 0~6 $N < 100, |x_i|, |y_i| < 1000$ 34
3 0~23 $N < 10^ 5, |x_i|, |y_i| < 10^ 9$ 31
4 0~38 $N < 10^ 6, |x_i|, |y_i| < 10^ 9$ 35

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