#P2029. Get Many Persimmon Trees
Get Many Persimmon Trees
题目描述
在18世纪,林清司(Seiji Hayashi)长期担任会津藩日新馆武士学校的教授。为表彰他在教育上的功绩,会津藩主松平容颂(Katanobu Matsudaira)决定赐予他一块位于会津盆地大田野中的矩形庄园。庄园的**宽度和高度**由藩主严格指定,但林教授可以自由选择庄园的位置。
田野中种植了许多日本柿子树(会津特产"无籽柿")。由于林教授特别喜爱柿子,他希望在自己的庄园内尽可能多地包含柿子树。
示例(图1):
- 整个田野是的矩形网格,每个
*
代表一棵柿子树。- 若庄园尺寸为(实线区域),最多包含棵树。
- 若为(虚线区域),最多棵。
- 若为(点线区域),最多棵。
- 注意:庄园的宽度和高度不可交换(与视为不同尺寸)。
输入格式
- 每个测试用例格式如下:
N W H x1 y1 x2 y2 ... xN yN S T
- :柿子树数量()。
- :田野的宽度和高度()。
- :第棵树的坐标(原点为,,,且所有坐标唯一)。
- :庄园的指定宽度和高度(,)。
- 输入以单独一行的结束。
输出格式
对每个测试用例,输出一行:庄园内最多可包含的柿子树数量。
样例输入
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0
样例输出
4 3