题目链接：
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);
}
}
Backspace