POJ 2932 Coneology——扫描线
  irtk7iI9MPj7 2023年11月02日 50 0


乍一看还以为线段树+扫描线,仔细想想虽然不是一个东西但是相似性很高,只要维护一下与扫描线相交的最外层圆就可以了,这里用了set,第一次写写得则乱,后来看了挑战程序设计才简化了代码,骚操作学到了

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxn = 40005;
int n;
double x[maxn], y[maxn], r[maxn];

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

void solve() {
vector<pair<double, int> > pos;
for (int i = 0; i < n; i++) {
pos.push_back(make_pair(x[i]-r[i], i));
pos.push_back(make_pair(x[i]+r[i], i+n));
}
sort(pos.begin(), pos.end());
set<pair<double, int> > s;
vector<int> ans;
for (int i = 0; i < pos.size(); i++) {
int id = pos[i].second % n;
if (pos[i].second < n) {
set<pair<double, int> >::iterator it = s.lower_bound(make_pair(y[id], id));
if (it != s.end() && inside(id, it->second)) continue;
if (it != s.begin() && inside(id, (--it)->second)) continue;
ans.push_back(id);
s.insert(make_pair(y[id], id));
}
else {
s.erase(make_pair(y[id], id));
}
}
sort(ans.begin(), ans.end());
printf("%d\n", ans.size());
for (int i = 0; i < ans.size(); i++) {
printf("%d%c", ans[i]+1, (i+1) == ans.size()?'\n':' ');
}
}

int main() {
while (~scanf("%d", &n)) {
for (int i = 0; i < n; i++) {
scanf("%lf %lf %lf", &r[i], &x[i], &y[i]);
}
solve();
}
return 0;
}


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  jJVxqmfuiDRw   2023年11月02日   59   0   0 sqli++System
irtk7iI9MPj7
作者其他文章 更多