HDU 4007 Dave 【双扫描线暴力】

比赛的时候用线段树做这题要么是不嫌麻烦就是贴标程了。。。那么水的题,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);
    }
}

posted on 2011-09-04 12:04 BUPT-[aswmtjdsj] @ Penalty 阅读(894) 评论(0)  编辑 收藏 引用 所属分类: 计算几何HDU Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜