题目描述
Farmer John wishes to build a corral for his cows. Being finicky beasts, they demand that the corral be square and that the corral contain at least C (1 <= C <= 500) clover fields for afternoon treats. The corral's edges must be parallel to the X,Y axes.
FJ's land contains a total of N (C <= N <= 500) clover fields, each a block of size 1 x 1 and located at with its lower left corner at integer X and Y coordinates each in the range 1..10,000. Sometimes more than one clover field grows at the same location; such a field would have its location appear twice (or more) in the input. A corral surrounds a clover field if the field is entirely located inside the corral's borders.
Help FJ by telling him the side length of the smallest square containing C clover fields.
约翰打算建一个围栏来圈养他的奶牛.作为最挑剔的兽类，奶牛们要求这个围栏必须是正方 形的，而且围栏里至少要有C< 500)个草场，来供应她们的午餐.
约翰的土地上共有C<=N<=500)个草场，每个草场在一块1x1的方格内，而且这个方格的 坐标不会超过10000.有时候，会有多个草场在同一个方格内，那他们的坐标就会相同.
告诉约翰，最小的围栏的边长是多少？
输入输出格式
输入格式：
Line 1: Two space-separated integers: C and N
Lines 2..N+1: Each line contains two space-separated integers that are the X,Y coordinates of a clover field.
输出格式：
Line 1: A single line with a single integer that is length of one edge of the minimum size square that contains at least C clover fields.
输入输出样例
3 41 22 14 15 2
4
说明
Explanation of the sample:
|* *
| * *
+------Below is one 4x4 solution (C's show most of the corral's area); many others exist.
|CCCC
|CCCC
|*CCC*
|C*C*
+------
#include#include using namespace std;#define maxn 4010int map[maxn][maxn],c,n,sum[maxn][maxn],N,M;int main(){ scanf("%d%d",&c,&n); int x,y; for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); map[x][y]++; N=max(N,x); M=max(M,y); } int range=max(N,M); for(int i=1;i<=range;i++) for(int j=1;j<=range;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]+map[i][j]-sum[i-1][j-1]; for(int i=1;i<=range;i++)//正方形的边长 for(int j=i;j<=range;j++) for(int k=i;k<=range;k++) if(sum[j][k]-sum[j-i][k]-sum[j][k-i]+sum[j-i][k-i]>=c){ printf("%d",i); return 0; }}