POJ2932Coneology（计算几何、平面扫描）

平面上有N NN个两两没有公共点的圆，i ii号圆的圆心在 ( x i , y i ) (x_i,y_i) (xi​,yi​),半径为 r i r_i ri​。求所有最外层的，即不包含与其他圆内部的圆。

解析：
利用垂直于x轴的线去从左往右扫描，观察点为圆的左右端点。因为圆是没有公共点的，这使得包含的判断变得简单。如果某个圆被包含那么一定是被最近的两个外圈的其中一个圆包含（y轴上），假设这个圆已经被包含，如果远的圆如果想包含这个圆必须把两个圆都包住，那么第一层包裹已经不再是外层。所以如果存在被包括在某个外层里，一定是被包裹在最近的两个外层的其中一个。
题解来源

https://paste.ubuntu.com/p/KvFfkzjvSH/

那位好心人帮我看看这个POJ上的题为啥一直Output Limit Exceeded（不是空格的问题）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<set>

using namespace std;
typedef long long ll;
typedef pair<double, int>PDL;
const int N = 50007, M = 5000007, INF = 0x3f3f3f3f;
set<PDL>out;
vector<int>ans;
int n, m;
int cnt, num;

struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }
};

struct Circle{
    double r;
    Point c;
    Circle(double r = 0, Point c = Point()):r(r), c(c) { }
    inline Point point(double a)
    {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
};
Circle C[N * 2];
inline Circle read_Circle()
{
    Circle C1;
    scanf("%lf%lf%lf", &C1.r, &C1.c.x, &C1.c.y);
    return C1;
}

PDL p[N * 2];
double x[N], y[N], r[N];
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];
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i){
        scanf("%lf%lf%lf", &r[i], &x[i], &y[i]);
		p[++num].first = x[i] - r[i];//左端点
		p[num].second = i;
		p[++num].first = x[i] + r[i];//右端点
		p[num].second = i + n;
    }
    sort(p + 1, p + 1 + num);

    for(int i = 1; i <= num; ++ i){
        int id = p[i].second;
        if(id <= n){//左端点
            set<PDL> :: iterator it = out.lower_bound(make_pair(y[id], id));
            if(it != out.end() && inside(id, it->second))continue;//被包含，不是答案，跳过
            if(it != out.begin() && inside(id, (--it)->second))continue;
            ans.push_back(id);
            out.insert(make_pair(y[id], id));//外圈
        }
        else {//到了这个圆的右端点该删除了，已经没用了，留着会影响答案
            id -= n;
            out.erase(make_pair(y[id], id));
        }
    }
    printf("%d\n", ans.size());
	sort(ans.begin(),ans.end());
	for(int i = 0; i < ans.size(); ++i)
		printf("%d ", ans[i]);

    return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<set>

using namespace std;
typedef long long ll;
typedef pair<double, int>PDL;
const int N = 50007, M = 5000007, INF = 0x3f3f3f3f;
set<PDL>out;
vector<int>ans;
int n, m;
int cnt;

struct Point{
    double x, y;
    Point(double x = 0, double y = 0):x(x), y(y){ }
};

struct Circle{
    double r;
    Point c;
    Circle(double r = 0, Point c = Point()):r(r), c(c) { }
    inline Point point(double a)
    {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
};
Circle C[N * 2];

PDL p[N * 2];

bool inside(int x, int y)
{
    double dx = C[x].c.x - C[y].c.x;
    double dy = C[x].c.y - C[y].c.y;
    return dx * dx + dy * dy <= C[x].r * C[y].r;
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i){
        scanf("%lf%lf%lf", &C[i].r, &C[i].c.x, &C[i].c.y);
        p[++ cnt].first = C[i].c.x - C[i].r;//左端点
        p[cnt].second = i;
        p[++ cnt].first = C[i].c.x + C[i].r;//右端点
        p[cnt].second = i + n;//区分左右端点
    }
    sort(p + 1, p + 1 + cnt);

    for(int i = 1; i <= cnt; ++ i){
        int id = p[i].second;
        if(id <= n){//左端点
            set<PDL> :: iterator it = out.lower_bound(make_pair(C[id].c.y, id));
            if(it != out.end() && inside(id, it->second))continue;//被包含，不是答案，跳过
            if(it != out.begin() && inside(id, (--it)->second))continue;
            ans.push_back(id);
            out.insert(make_pair(C[id].c.y, id));//外圈
        }
        else {//到了这个圆的右端点该删除了，已经没用了，留着会影响答案
            id -= n;
            out.erase(make_pair(C[id].c.y, id));
        }
    }
    printf("%d\n", ans.size());
	sort(ans.begin(), ans.end());
	for(int i = 0; i < ans.size(); ++i)
		printf("%d ", ans[i]);

    return 0;
}