比赛的时候用线段树做这题要么是不嫌麻烦就是贴标程了。。。那么水的题,1000的数据范围,果断N^2暴力啊。。
场上的时候claire大神瞬间1A,太犀利了。
维护四根双维度扫描线。
把读入的点copy一遍,一组x排序,一组y排序,用于两种扫描线的统计。
两根水平的,一左一右,保证距离不大于R;两根竖直的,用于统计,保证距离不大于R,且对于线框内的每个点判断是否在水平两根线的范围内,如果是则计数器加1,且当下扫描线上移时,如果是已经统计过的点则计数器减1。整体的思想类似队列。
附代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 1005
struct point
{
int x,y;
point(){}
point(int a,int b):x(a),y(b){}
}ver[maxn],par[maxn];
bool cmpx(point a,point b)
{
return a.x < b.x;
}
bool cmpy(point a,point b)
{
return a.y < b.y;
}
int n,R;
int main()
{
while(scanf("%d %d",&n,&R) == 2)
{
for(int i = 0;i < n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
ver[i] = point(a,b);
par[i] = point(a,b);
}
sort(ver,ver + n,cmpy);
sort(par,par + n,cmpx);
int posl,posr,posu,posd;
int l = 0,r = 0,u = 0,d = 0;
int ans = 0;
for(l = 0;l < n;l++)
{
posl = par[l].x;
while(par[r].x - posl <= R && r < n)
r++;
posr = par[r - 1].x;
u = 0;
int temp = 0;
for(d = 0;d < n;d++)
{
posd = ver[d].y;
if(d != 0 && ver[d - 1].x <= posr && ver[d - 1].x >= posl)
temp--;
for(;u < n;u++)
{
if(ver[u].y - posd > R)
break;
if(ver[u].x >= posl && ver[u].x <= posr)
temp++;
}
ans = max(ans,temp);
if(u == n - 1)
break;
}
}
printf("%d\n",ans);
}
}
å