2054 . 最大矩形涵蓋（cover）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb a
$輸\tiny 光光$

User's AC Ratio

81.6% (40/49)

Submission's AC Ratio

29.6% (55/186)

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

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