学步园

参考了这篇博客的代码：ZOJ 3521 Fairy Wars【并查集，扫描线，set维护】 - From A Start,As An Acmer - C++博客

这道题融合了两种算法，既有图论也有计算几何，但总体上不算难。

题目大意为：在平面上有一些子弹，如果子弹被冰冻那么以炸弹为中心的，边长为L的正方形以内的子弹都会被冰冻，从而引发连锁反应。现在放法术让以x0和y0为圆心，r为半径的圆内的所以子弹冰冻，求最后会有多少颗子弹被冰冻。

并查集找出所有联通块：先对点按x排序，维护两个指针，把点一次加入set中【按y排序，为了避开重点，second选值为点的序号】，一头一尾，首先都指向数组头部。然后移动尾部，必要时移动头部使得两指针间的点的x间距恰不大于L/2，然后每填加进一个点都判断和前一个点和后一个点的y间距是否大于L/2，如果符合条件，则加入同一个集合。

最后暴力搜一遍和点(x0, y0)距离小于r的点，找出所有相交的集合即可。

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <set>
#define LL long long

using namespace std;

const int maxn = 50005;

typedef struct Point
{
        LL x, y;
        Point() {}
        Point(LL _x, LL _y):
                x(_x), y(_y) {}
        Point operator -(const Point &argu) const
        {
                return Point(x - argu.x, y - argu.y);
        }
        bool operator <(const Point &argu) const
        {
                if(x == argu.x)
                        return y < argu.y;
                return x < argu.x;
        }
        LL len2()
        {
                return x * x + y * y;
        }
}pp;

pp p[maxn], c;

typedef set< pair<LL, int> > ss;
ss s;
ss::iterator it;

LL ABS(LL x)
{
        return x >= 0 ? x : -x;
}

int n, l;
LL r;
int f[maxn], range[maxn];
bool vis[maxn];

int find_baba(int x)
{
        return x == f[x] ? x : f[x] = find_baba(f[x]);
}

void uni(int a, int b)
{
        int fa = find_baba(a);
        int fb = find_baba(b);
        if(fa != fb)
        {
                f[fb] = fa;
                range[fa] += range[fb];
        }
}

void work()
{
        s.clear();
        int st = 0;
        int a, b;
        for(int i = 0; i < n; i++)
        {
                while(ABS(p[i].x - p[st].x) > l)
                {
                        s.erase(make_pair(p[st].y, st));
                        st++;
                }
                it = s.insert(make_pair(p[i].y, i)).first; //返回插入元素地址
                if(it != s.begin())
                {
                        it--;
                        if(ABS(p[i].y - (it->first)) <= l)
                        {
                                a = i;
                                b = it->second;
                                uni(a, b);
                        }
                        it++;
                }
                it++;
                if(it != s.end() && ABS(p[i].y - (it->first)) <= l)
                {
                        a = i;
                        b = it->second;
                        uni(a, b);
                }
        }
}

int main()
{
//        freopen("3521.in", "r", stdin);

        while(~scanf("%d%lld%d", &n, &r, &l))
        {
                fill(range, range + n, 1);
                l /= 2;
                for(int i = 0; i < n; i++)
                        f[i] = i;
                for(int i = 0; i < n; i++)
                        scanf("%lld%lld", &p[i].x, &p[i].y);
                sort(p, p + n);
                scanf("%lld%lld", &c.x, &c.y);
                work();
                int ans = 0;
                memset(vis, 0, sizeof(vis));
                for(int i = 0; i < n; i++)
                {
                        if((p[i] - c).len2() <= r * r)
                        {
                                int ba = find_baba(i);
                                if(!vis[ba])
                                {
                                        ans += range[ba];
                                        vis[ba] = true;
                                }
                        }
                }
                printf("%d\n", ans);
        }
        return 0;
}