ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】

题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3521
以前一直以为扫描线这么神奇的想法应该有很复杂的代码,今天亲身写了一下,发现只要数据结构维护的好,代码真的很短。
感谢wolf5x大神、schnee大神对我这蒟蒻的指导。

题目大意:有一个圆形炸弹,给定二维坐标和半径;平面上N个点(N<=50000),每个点的二维坐标给出;给定一个L,是这些点的影响范围,影响范围是以这个点为中心的长度为L的正方形;影响范围内的点可以互相影响,连锁具有传递性。问,把炸弹引爆的话,会有多少个点被连锁。

做法:扫描线+set维护+并查集+枚举(最后一个随便说说。。。)

具体:裸的想法就是连边并查集,这个是O(N^2)的复杂度,铁挂;几何题的自然想法就是想到极角排序和扫描线以及线段树上面去。
极角排序没有好想法,线段树不会搞,就想扫描线+set维护的神想法。
一开始想环形扫描线想不出个所以然来,经大神们点拨后开始拿传统的坐标序扫描线搞之。

将这N个点按x坐标排序,维护两根扫描线或者说一个队列,一开始队列头尾都指向最左点,队列尾向右移动的时候先判断头尾两点的横坐标差值是否大于L,大于则把对头右移直到满足条件,同时将弹队的这些点在set中删除:

set中的元素是一个pair,first是点的纵坐标,second是点的id,这样就保证了内部没有重复元素,内部序按照y排序;然后将队尾的元素插入set中,因为插入函数的返回值是一个pair,pair的first即为队尾的点在set中的插入位置,second是插入成功与否的bool。

所以it-1(it != set.begin() )和it+1(it+1 != set.end() )分别是set中与当前插入点y坐标最相近的两个点,比较当前点与这两个的y坐标之差是否小于等于L,是则union之。可以归纳证明,需要判断的只有最近的两个点,因为更远的点已经在之前判断过了。

这样扫描一遍过后,就剩下几个联通块;再扫描一遍,判断圆是否与某个联通块相交,若相交则将联通块大小加到答案上,最后输出答案即可。

注意点:
1.为了防止浮点数误差,判断点在圆内的时候,直接用整数平方判断的,所以会超int,注意long long。
2.维护的时候注意尽量少写特判语句,比如初始点什么的,用一个统一化的判断语句来判断弹队与否,比如front 与 tail的距离什么的。。
3.set的insert函数的返回值的first是个指针,所以当我们插入的元素即为一个pair时,访问pair的first需要用->而非.
4.set的元素是一一对应的,无重复元素;用insert来实现find的功能,原因在于set没有单关键字查询功能,或者说没有我们想要的对于pair内某一元素的查询功能,所以用insert来实现find,是一个更巧妙的想法。
5.我是个蒟蒻,又tmd把并查集写错了。
6.思维比较神的题、各种算法联合在一起的题目不一定需要很大的代码量,不要被吓住。

附上代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
#include 
<set>
#include 
<queue>
#include 
<algorithm>
#include 
<cstdlib>
#include 
<vector>
#define maxn 50005
using namespace std;
struct point
{
    
long long x,y;
    point(){}
    point(
long long _x,long long _y):x(_x),y(_y){}
    point 
operator -(const point p)
    {
        
return point(x - p.x,y - p.y);
    }
    
long long norm2()
    {
        
return x * x + y * y;
    }
}p[maxn],c;
typedef 
set <pair<long long,int> > SET;
SET S;
SET::iterator it;
long long ab(long long x)
{
    
return x >= 0?x : -x;
}
bool cmp(const point &a,const point &b)//for sort
{
    
return a.x < b.x;
}
int n,l;
long long r;
int f[maxn],ra[maxn];
bool has[maxn];
int find(int x)
{
    
return x == f[x] ? x : f[x] = find(f[x]);
}
void un(int a,int b)
{
    a 
= find(a);
    b 
= find(b);
    
if(a != b)
    {
        
if(ra[a] > ra[b])
        {
            f[b] 
= a;
            ra[a] 
+= ra[b];
        }
        
else
        {
            f[a] 
= b;
            ra[b] 
+= ra[a];
        }
    }
}
void gao()
{
    S.clear();
    
int front = 1;
    
int a,b;
    
for(int i = 1;i <= n;i++)
    {
        
while(ab(p[i].x - p[front].x) > l)
        {
            S.erase(make_pair(p[front].y,front));
            front
++;
        }
        it 
= S.insert(make_pair(p[i].y,i)).first;
        
if(it != S.begin())
        {
            it
--;
            
if(ab(p[i].y - (it -> first)) <= l)
            {
                a 
= i;
                b 
= it -> second;
                un(a,b);
            }
            it
++;
        }
        it
++;
        
if(it != S.end() && ab(p[i].y - (it -> first)) <= l)
        {
            a 
= i;
            b 
= it -> second;
            un(a,b);
        }
    }
}
int main()
{
    
while(scanf("%d %lld %d",&n,&r,&l) == 3)
    {
        fill(ra,ra 
+ n + 1,1);
        l 
/= 2;
        
for(int i = 1;i <= n;i++)
            f[i] 
= i;
        
for(int i = 1;i <= n;i++)
            scanf(
"%lld %lld",&p[i].x,&p[i].y);
        sort(p 
+ 1,p + n + 1,cmp);
        scanf(
"%lld %lld",&c.x,&c.y);
        gao();
        
int ans = 0;
        memset(has,
0,sizeof(has));
        
for(int i = 1;i <= n;i++)
        {
            
if((p[i] - c).norm2() <= r * r)
            {
                
int fuck = find(i);
                
if(!has[fuck])
                {
                    ans 
+= ra[fuck];
                    has[fuck] 
= true;
                }
            }
        }
        printf(
"%d\n",ans);
    }
}

posted on 2011-08-29 20:45 BUPT-[aswmtjdsj] @ Penalty 阅读(1505) 评论(5)  编辑 收藏 引用 所属分类: 计算几何ZOJ Solution Report

评论

# re: ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】 2011-08-31 18:17 unasm

你stl用的太。。。  回复  更多评论   

# re: ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】 2011-08-31 18:31 BUPT-[aswmtjdsj] @ Penalty

@unasm
stl用的太少~~~不好意思见笑了~~~  回复  更多评论   

# re: ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】 2011-08-31 19:48 unasm

我都研究两天了。就是不懂那个 it = S.insert(make_pair(p[i].y,i)).first;不是太少,而是太神  回复  更多评论   

# re: ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】 2011-08-31 20:06 BUPT-[aswmtjdsj] @ Penalty

@unasm
呃。。这个去看看C++ reference吧。。。set的insert函数返回了一个pair。。。  回复  更多评论   

# re: ZOJ 3521 Fairy Wars【并查集,扫描线,set维护】 2014-11-11 16:34 someone

【 it = S.insert(make_pair(p[i].y,i)).first】不知是否是理解错误,个人觉得一句是返回插入元素的地址。  回复  更多评论   


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


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

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜