2054 . 最大矩形涵蓋（cover）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb vqv4lsq
icube
baluteshih 好強 <(_ _)>

User's AC Ratio

82.6% (128/155)

Submission's AC Ratio

34.1% (181/531)

Tags

TOI 2018-TOI-pre

Description

彼得是提歐埃國的一名網路工程師，在研發的過程中遭遇了一個難題，希望你能夠幫助他解決，問題的描述如下。
給定一個長度為$l$寬度為$w$的矩形以及$n$個平面上相異的座標點，每個點代表提歐埃國的一個城市，彼得想要知道：在可以任意平移（不可旋轉）矩形的情況下，矩形範圍內能夠涵蓋到的最多城市數量。（城市座標點落在矩形範圍內或邊界上視為覆蓋。）
下圖(a)為7座城市的例子，若矩形的長度為3且寬度為5，(b)紅色匡現為一種可能的矩形位置，涵蓋了4個城市，下圖(c)為涵蓋最多城市的矩形位置，涵蓋了5個城市。

​

給定長$l$寬$w$的矩形以及$n$個相異的城市座標點，請撰寫一支程式幫助彼得算出此矩形範圍能夠涵蓋到的最多城市數量。

Input Format

每筆測資的第一行有三個正整數$n(1\leq n \leq 3000)$，$l$和$w(1\leq l, w \leq 1000000)$，分別代表城市數量、矩形的長度和矩形的寬度。
接下來有$n$行輸入，每一行有兩個整數$x$和$y(0 \leq x, y\leq 1000000)$，代表一座城市的$x$軸坐標和$y$軸座標。

子任務（測資） 額外限制 分數
1 (0~14) 所有城市的$y$座標值皆為0（如範例1） 20
2 (15~34) $l = 1$且所有城市的$y$座標值皆為偶數（如範例2） 30
3 (35~61) 無（如範例3） 50

Output Format

輸出為一整數，代表矩形範圍可以涵蓋的最多城市數量。

Sample Input

Sample Input #1
5 1 4
7 0
4 0
0 0
5 0
9 0

Sample Input #2
8 1 3
7 2
2 2
5 2
1 8
9 8
6 6
5 6
3 6

Sample Input #3
7 3 5
1 3
7 2
5 3
7 4
1 5
3 4
4 2

Sample Output

Sample Output #1
3

Sample Output #2
3

Sample Output #3
5

Hints

Problem Source

2018 TOI入營考pD

Subtasks

No. Testdata Range Score
1 0~14 20
2 15~34 30
3 35~61 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 1
6 1000 262144 262144 1
7 1000 262144 262144 1
8 1000 262144 262144 1
9 1000 262144 262144 1
10 1000 262144 262144 1
11 1000 262144 262144 1
12 1000 262144 262144 1
13 1000 262144 262144 1
14 1000 262144 262144 1
15 1000 262144 262144 2
16 1000 262144 262144 2
17 1000 262144 262144 2
18 1000 262144 262144 2
19 1000 262144 262144 2
20 1000 262144 262144 2
21 1000 262144 262144 2
22 1000 262144 262144 2
23 1000 262144 262144 2
24 1000 262144 262144 2
25 1000 262144 262144 2
26 1000 262144 262144 2
27 1000 262144 262144 2
28 1000 262144 262144 2
29 1000 262144 262144 2
30 1000 262144 262144 2
31 1000 262144 262144 2
32 1000 262144 262144 2
33 1000 262144 262144 2
34 1000 262144 262144 2
35 1000 262144 262144 3
36 1000 262144 262144 3
37 1000 262144 262144 3
38 1000 262144 262144 3
39 1000 262144 262144 3
40 1000 262144 262144 3
41 1000 262144 262144 3
42 1000 262144 262144 3
43 1000 262144 262144 3
44 1000 262144 262144 3
45 1000 262144 262144 3
46 1000 262144 262144 3
47 1000 262144 262144 3
48 1000 262144 262144 3
49 1000 262144 262144 3
50 1000 262144 262144 3
51 1000 262144 262144 3
52 1000 262144 262144 3
53 1000 262144 262144 3
54 1000 262144 262144 3
55 1000 262144 262144 3
56 1000 262144 262144 3
57 1000 262144 262144 3
58 1000 262144 262144 3
59 1000 262144 262144 3
60 1000 262144 262144 3
61 1000 262144 262144 3
Submit
Status
Ranklist
Back to Top