POJ 2932 平面扫描

题意：

平面上有N个两两没有公共点的圆，i号圆的圆心在(xi,yi)，半径为ri。求所有最外层的，即不包含于其他圆内部的圆。

分析：

在几何问题中，我们经常利用平面扫描技术来降低算法的复杂度。所谓平面扫描，是指扫描线在平面上按给定的轨迹移动的同时，不断根据扫描线扫过的部分更新信息，从而得到整体所要求得结果的方法。扫描的方法，既可以从左向右平移与y轴平行的直线，也可以固定射线的端点逆时针转动。

 

对于这道题，我们从左向右平移与y轴平行的直线的同时，维护与扫描线相交的最外层的圆的集合。从左向右移动的过程中，只有扫描线移动到圆的左右两端时，圆与扫描线的相交关系才会发生变化，因此我们先将所有的这样的x坐标枚举出来并排好序。

首先，我们来看一下扫描线移动到某个圆的左端时的情况。此时，我们需要判断该圆是否包含在其他圆中。为此，我们只需从当前与扫描线相交的最外层的圆中，找到上下两侧y坐标方向距离最近的两个圆，并检查他们就足够了。这是因为，假设该圆被包含于更远的圆中，却不被包含于最近的圆中，就会如下图所示，得出两圆相交的结论。而这与题目所给的条件不符。于是，只要用二叉查找树来维护这些圆，就能够在O(logn)时间内取得待检查的圆了。

 

其次，我们看一下扫描线移动到某个圆的右端时的情形。此时的处理很简单，如果该圆已经包含于其他圆中就什么也不做，如果是最外层的圆就将它从二叉树中删去。综上，总的复杂度为O(nlogn)。

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
const int maxn = 40000 + 10;
 
int n;
double x[maxn], y[maxn], r[maxn];
 
//判断圆i是否在圆j的内部
bool inside(int i, int j)
{
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return dx * dx + dy * dy <= r[j] * r[j];
}
 
void solve()
{
    //枚举关键点
    vector<pair<double, int> > events;   //圆的左右两端的x坐标
    for (int i = 0; i < n; i++){
        events.push_back(make_pair(x[i] - r[i], i));    //圆的左端
        events.push_back(make_pair(x[i] + r[i], i + n));    //圆的右端
    }
    sort(events.begin(), events.end());
 
    //平面扫描
    set<pair<double, int> > outers;   //与扫描线相交的最外层的圆的集合
    vector<int> res;     //最外层圆的列表
    for (int i = 0; i < events.size(); i++){
        int id = events[i].second % n;
        if (events[i].second < n){        //扫描到左端
            set<pair<double, int> > :: iterator it = outers.lower_bound(make_pair(y[id], id));
            if (it != outers.end() && inside(id, it -> second))
                continue;
            if (it != outers.begin() && inside(id, (--it) -> second))
                continue;
            res.push_back(id);
            outers.insert(make_pair(y[id], id));
        }
        else{        //扫描到右端
            outers.erase(make_pair(y[id], id));
        }
    }
 
    sort(res.begin(), res.end());
    printf("%d\n", res.size());
    for (int i = 0; i < res.size(); i++){
        printf("%d%c", res[i] + 1, i + 1 == res.size() ? '\n' : ' ');
    }
}
 
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%lf%lf%lf", &r[i], &x[i], &y[i]);
    }
    solve();
    return 0;
}

转自：https://blog.csdn.net/a2459956664/article/details/51416881

参考资料：程序挑战