HDu 4007 Dave(2011年大連ACMネット試合)
标题:与えられた正方形の辺長rは、平面内で正方形が囲む点の最大個数を探す.
解析:まず点を並べ替えてから、1つのエッジを固定し、もう1つの垂直エッジを平行移動して、点の数を得て、最後にサイズを比較します.
注意:正方形の傾斜が含まれていない場合!
解析:まず点を並べ替えてから、1つのエッジを固定し、もう1つの垂直エッジを平行移動して、点の数を得て、最後にサイズを比較します.
注意:正方形の傾斜が含まれていない場合!
// Time 125ms; Memory 240k#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct point
{
int x,y;
};
bool operator < (point a,point b)
{
return a.x<b.x;
}
int main()
{
int i,j,k,l,n,r,t,cnt,mx,q[1010];
point p[1010];
while(scanf("%d%d",&n,&r)!=EOF)
{
for(i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
sort(p,p+n);
mx=0;t=-1;
for(i=0;i<n-mx;i++) if(p[i].x!=t)
{
k=0;
t=p[i].x;
for(j=i;j<n;j++)
{
if(p[j].x-p[i].x-r>0) break;
q[k++]=p[j].y;
}
sort(q,q+k);
l=0;
for(j=0;j<k;j++)
{
while(q[j]-q[l]>r) l++;
cnt=j+1-l;
if(mx<cnt) mx=cnt;
}
}
printf("%d
",mx);
}
return 0;
}