首页 > 代码库 > POJ 2932 Coneology（扫描线）
POJ 2932 Coneology（扫描线）
【题目链接】 http://poj.org/problem?id=2932
【题目大意】
给出N个两两没有公共点的圆，求所有不包含于其它圆内部的圆
【题解】
我们计算出所有点在圆心所有y位置的x值，
由于两两没有公共点，所以当我们对所有的x坐标进行扫描时，只要扫描相邻的x，
判定扫描到的圆和与其x相邻的圆是否是圆包含关系就可以判断一个圆的位置
扫描到左端点时，如果圆其被包含，则什么都不做，否则，将这个圆加入set中，
当扫描到右端点时，如果圆被包含，则什么都不做，否则将圆从set中去除。
【代码】
#include <cstdio>#include <algorithm>#include <vector>#include <set>using namespace std;const int MAX_N=40010;int N;double x[MAX_N],y[MAX_N],r[MAX_N];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> >events; 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‘:‘ ‘); }}void init(){ for(int i=0;i<N;i++)scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);}int main(){ while(~scanf("%d",&N)){ init(); solve(); }return 0;}
POJ 2932 Coneology（扫描线）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。