1487 . 遺址之謎

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

28.6% (2/7)

Tags

ytp ytp2026 ytp-senior

Description

某個遺址橫跨一片廣闊的平原。考古隊在地面上鋪設了棋盤狀的繩索網格，將遺址劃分成整齊的方格區域。為了保護尚未發掘的地層，研究員只能沿著繩索上下左右行走。一步代表沿繩索移動一格。兩個發掘點之間的距離為它們之間所需的最少步數。

考古隊在遺址內共標記了 $n$ 個發掘點，每個發掘點都位於繩索的某個交叉口上。隊長翻閱古代文獻時，發現一個反覆出現的神秘數字 $d$，相信這是當時規劃遺址時採用的標準距離，標記著有特殊關聯的一對地點。他想知道，這 $n$ 個發掘點中，有幾對恰好相距 $d$ 步？

Input Format

第一行有兩個正整數 $n$ 和 $d$，分別代表發掘點數量與神秘數字。

接下來 $n$ 行，每行有兩個整數 $x_i$ 和 $y_i$，代表第 $i$ 個發掘點的座標。

  • $1 \leq n \leq 10^ 6$
  • $1 \leq d \leq 2 \times 10^ 9$
  • $|x_i|, |y_i| \leq 10^ 9$
  • 所有發掘點的位置互不相同

Output Format

輸出一個整數，代表恰好相距 $d$ 步的發掘點對數。

Sample Input 1

5 3
0 0
3 0
0 3
-3 0
1 2

Sample Output 1

4

Hints

範測 1 解釋：

恰好相距 $3$ 步的發掘點對為 $(0,0)$ 與 $(3,0)$、$(0,3)$、$(-3,0)$、$(1,2)$，共 $4$ 對。

Problem Source

2026 YTP 高中組初賽 p7

Subtasks

No. Testdata Range Constraints Score
1 0 範例測試資料 0
2 0~10 $n \leq 3000$ 2
3 0, 11~18 $n \times d \leq 10^ 7$ 6
4 0~28 無額外限制 12

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 1048576 65536 1 2 3 4
1 5000 1048576 65536 2 4
2 5000 1048576 65536 2 4
3 5000 1048576 65536 2 4
4 5000 1048576 65536 2 4
5 5000 1048576 65536 2 4
6 5000 1048576 65536 2 4
7 5000 1048576 65536 2 4
8 5000 1048576 65536 2 4
9 5000 1048576 65536 2 4
10 5000 1048576 65536 2 4
11 5000 1048576 65536 3 4
12 5000 1048576 65536 3 4
13 5000 1048576 65536 3 4
14 5000 1048576 65536 3 4
15 5000 1048576 65536 3 4
16 5000 1048576 65536 3 4
17 5000 1048576 65536 3 4
18 5000 1048576 65536 3 4
19 5000 1048576 65536 4
20 5000 1048576 65536 4
21 5000 1048576 65536 4
22 5000 1048576 65536 4
23 5000 1048576 65536 4
24 5000 1048576 65536 4
25 5000 1048576 65536 4
26 5000 1048576 65536 4
27 5000 1048576 65536 4
28 5000 1048576 65536 4
Submit
Back to Top