Description
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.
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
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.
The end of the input is indicated by a line that solely contains a zero.
Output
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
Sample Output
4
3
【题意】给出一个n*m的土地,圈一个w*h的小块地,要求有最多的trees;
【思路】枚举所有可能的圈地方式,用二维树状数组算出该圈地得到了多少个*,取最大结果输出
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
const int N=;
int c[N][N];//二维树状数组
int n,m;
int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y)
{
for(int i=x;i<=n;i+=lowbit(i))
{
for(int j=y;j<=m;j+=lowbit(j))
{
c[i][j]++;
}
}
}
int get_sum(int x,int y)
{
int ans=;
for(int i=x;i>=;i-=lowbit(i))
for(int j=y;j>=;j-=lowbit(j))
{
ans+=c[i][j];
}
return ans;
}
int main()
{
int t;
while(scanf("%d",&t),t)
{
memset(c,,sizeof(c));
scanf("%d%d",&n,&m);
for(int i=;i<t;i++)
{
int x,y;
scanf("%d%d",&x,&y);
update(x,y); }
int w,h;
scanf("%d%d",&w,&h);
int ans=-;
for(int i=w;i<=n;i++)//枚举
{
for(int j=h;j<=m;j++)
{
int tmp=get_sum(i,j)-get_sum(i,j-h)-get_sum(i-w,j)+get_sum(i-w,j-h);//求子矩形中的tree的数量
if(ans<tmp)
ans=tmp;
}
}
printf("%d\n",ans);
}
return ;
}