求n個(gè)圓中沒(méi)有被包含的圓。模仿掃描線從左往右掃，到左邊界此時(shí)如有3個(gè)交點(diǎn)，則有3種情況，以此判定該圓是否被離它最近的圓包含，而交點(diǎn)和最近的圓可以用以y高度排序的Set來(lái)維護(hù)。因此每次到左邊界插入該圓，找該圓最近的兩個(gè)圓（上方和下方）判斷是否包含，到右邊界則從Set中刪除該圓。

/** @Date : 2017-08-13 17:27:55* @FileName: POJ 2932 圓掃描線.cpp* @Platform: Windows* @Author : Lweleth (SoungEarlf@gmail.com)* @Link : https://github.com/* @Version : $Id$*/ #include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <utility> #include <vector> #include <map> #include <set> #include <string> #include <stack> #include <queue> #include <math.h> #define LL long long #define PII pair<int ,int> #define MP(x, y) make_pair((x),(y)) #define fi first #define se second #define PB(x) push_back((x)) #define MMG(x) memset((x), -1,sizeof(x)) #define MMF(x) memset((x),0,sizeof(x)) #define MMI(x) memset((x), INF, sizeof(x)) using namespace std;const int INF = 0x3f3f3f3f; const int N = 1e5+20; const double eps = 1e-8;int n; struct circle {double x, y, r;circle(){}circle(double _x, double _y, double _r){x = _x, y = _y, r = _r;} };circle c[N]; pair<double, int>p[N*2]; int ans[N];int isinside(int a, int b) {double dx = c[a].x - c[b].x;double dy = c[a].y - c[b].y;return dx * dx + dy * dy <= c[b].r * c[b].r; }int main() {scanf("%d", &n);for(int i = 0; i < n; i++){double x, y, r;scanf("%lf%lf%lf", &r, &x, &y);c[i] = circle(x, y, r);}for(int i = 0; i < n; i++){p[i*2] = MP(c[i].x - c[i].r, i);p[i*2 + 1] = MP(c[i].x + c[i].r, i + n);}sort(p, p + 2 * n);set<pair<double, int> >q;int cnt = 0;for(int i = 0; i < 2 * n; i++){if(p[i].se < n){set<pair<double, int> >::iterator it;/*auto */it = q.lower_bound(MP(c[p[i].se].y, p[i].se));if(it != q.end() && isinside(p[i].se, it->se)|| it != q.begin()&&isinside(p[i].se, (--it)->se))continue;q.insert(MP(c[p[i].se].y, p[i].se));ans[cnt++] = p[i].se;}else q.erase(MP(c[p[i].se%n].y, p[i].se%n)); }sort(ans, ans + cnt);printf("%d\n", cnt);for(int i = 0; i < cnt; i++)printf("%d%s", ans[i] + 1, i==cnt-1?"\n":" ");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Yumesenya/p/7688240.html

總結(jié)

以上是生活随笔為你收集整理的POJ 2932 圆扫描线的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。