Get Many Persimmon Trees --- 2003年 会津大会 国内予選 問題B

[ Problem ]
 Seiji Hayashi had been a professor of the Nisshinkan Samurai School in the domain of Aizu for a long time in the 18th century. In order to reward him for his meritorious career in education, Katanobu Matsudaira, the lord of the domain of Aizu, had decided to grant him a rectangular estate within a large field in the Aizu Basin. Although the size (width and height) of the estate was strictly specified by the lord, he was allowed to choose any location for the estate in the field. Inside the field which had also a rectangular shape, many Japanese persimmon trees, whose fruit was one of the famous products of the Aizu region known as 'Mishirazu Persimmon', were planted. Since persimmon was Hayashi's favorite fruit, he wanted to have as many persimmon trees as possible in the estate given by the lord.
 「教育における功績のご褒美として、会津の大名から四角い土地をもらえることになった。サイズは大名が決めるが、土地の場所はブロック内ならどこでもいいらしい。ブロック内に、会津名物の柿木があちこちに植えてあったので、できるだけ多くの木を囲む土地を選びたい。」

 For example, in Figure 1, the entire field is a rectangular grid whose width and height are 10 and 8 respectively. Each asterisk (*) represents a place of a persimmon tree. If the specified width and height of the estate are 4 and 3 respectively, the area surrounded by the solid line contains the most persimmon trees. Similarly, if the estate's width is 6 and its height is 4, the area surrounded by the dashed line has the most, and if the estate's width and height are 3 and 4 respectively, the area surrounded by the dotted line contains the most persimmon trees. Note that the width and height cannot be swapped; the sizes 4 by 3 and 3 by 4 are different, as shown in Figure 1.
 「例えば、図1に横10縦8のブロックを表す。アスタリスク (*) は木の植えてある場所を示す。横幅4高さ3サイズの土地なら、実線で囲んだ土地に木が最も多い。横幅6高さ4の土地ならダッシュで示したものが最も木が多い。横幅3高さ4の土地なら点線の土地が最も理想的だ。ただし、注意して欲しいのは、横幅と高さを入れ替えてはいけないこと。つまり、3x4と4x3は違うサイズ。」


Figure 1: Examples of Rectangular Estates

 Your task is to find the estate of a given size (width and height) that contains the largest number of persimmon trees.
 「与えられたサイズ(横幅と高さ)に対し、最も多くの柿木を囲む土地の場所を決めてくれ。」

[ Input ]
 The input consists of multiple data sets. Each data set is given in the following format.
 「入力に複数のデータセットを含む。各データセットのフォーマットは以下の通り。」

   N
   W H
   x1 y1
   x2 y2
   ...
   xN yN
   S T

 N is the number of persimmon trees, which is a positive integer less than 500. W and H are the width and the height of the entire field respectively. You can assume that both W and H are positive integers whose values are less than 100. For each i (1 <= i <= N), xi and yi are coordinates of the i-th persimmon tree in the grid. Note that the origin of each coordinate is 1. You can assume that 1 <= xi <= W and 1 <= yi <= H, and no two trees have the same positions. But you should not assume that the persimmon trees are sorted in some order according to their positions. Lastly, S and T are positive integers of the width and height respectively of the estate given by the lord. You can also assume that 1 <= S <= W and 1 <= T <= H.
 「N (500未満の正の整数)、柿木の数。W, H (それぞれ100未満の正の整数)、ブロックの横幅と高さ。xi, yi、i番目の木の位置。座標の原点は1であることに注意。同じ座標に木が2本以上あることはないが、座標の順番はソートされていない。S, T、大名から与えられた土地の横幅と高さ。」

 The end of the input is indicated by a line that solely contains a zero.
 「入力の終了として、最後の行に0が入る。」

[ Output ]
 For each data set, you are requested to print one line containing the maximum possible number of persimmon trees that can be included in an estate of the given size.
 「それぞれのデータセットに対し、与えられたサイズの土地で囲める最大の柿木の本数を1行ずつ出力せよ。」

[ Sample Input ]
16
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

[ Output for the Sample Input ]
4
3

Comments are closed.

Post Navigation