2234 . 2D Chess Without Multiverse Time Travel
TopCoder
Tags
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 1
4
0 0
1 1
0 1
-1 -1
0 0
1 1
0 1
-1 -1
Sample Output 1
4
Sample Input 2
4
-5 5
5 5
5 -5
-5 -5
-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, |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 |