2054 . 最大矩形涵蓋（cover）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

85.4% (187/219)

Submission's AC Ratio

37.6% (266/708)

Tags

TOI TOI-pre 2018-TOI-pre

Description

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

​

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

Input Format

每筆測資的第一行有三個正整數n(1≤n≤3000)，l和w(1≤l,w≤1000000)，分別代表城市數量、矩形的長度和矩形的寬度。
接下來有n行輸入，每一行有兩個整數x和y(0≤x,y≤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 1

5 1 4
7 0
4 0
0 0
5 0
9 0

Sample Output 1

3

Sample Input 2

8 1 3
7 2
2 2
5 2
1 8
9 8
6 6
5 6
3 6

Sample Output 2

3

Sample Input 3

7 3 5
1 3
7 2
5 3
7 4
1 5
3 4
4 2

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 (VSS, 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
Back to Top