首页 > 代码库 > poj 2932 Coneology (扫描线)
poj 2932 Coneology (扫描线)
题意
平面上有N个两两不相交的圆,求全部最外层的,即不被其它圆包括的圆的个数并输出
思路
挑战程序竞赛P259页
代码
/* **********************************************
Auther: xueaohui
Created Time: 2015-7-25 16:56:13
File Name : poj2932.cpp
*********************************************** */
#include <iostream>
#include <fstream>
#include <cstring>
#include <climits>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <bitset>
#include <functional>
#include <algorithm>
using namespace std;
#define ll long long
#define N 111111
int n;
double x[N],y[N],r[N];
bool inside(int i,int j){
double px = x[i]-x[j];
double py = y[i]-y[j];
return px*px+py*py<=r[j]*r[j];
}
void slove(){
vector<pair<double,int>>e;
e.clear();
for(int i=0;i<n;i++){
e.push_back(make_pair(x[i]-r[i],i));
e.push_back(make_pair(x[i]+r[i],i+n));
}
sort(e.begin(),e.end());
set<pair<double,int>>out;
vector<int>res;
res.clear();
out.clear();
for(int i=0;i<e.size();i++){
int id = e[i].second %n;
if(e[i].second<n){
set<pair<double,int>>::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;
res.push_back(id);
out.insert(make_pair(y[id],id));
}
else{
out.erase(make_pair(y[id],id));
}
}
sort(res.begin(),res.end());
printf("%d\n",res.size());
for(int i=0;i<res.size();i++){
if(i!=0) printf(" ");
printf("%d",res[i]+1);
}
printf("\n");
}
int main(){
while(scanf("%d",&n)==1){
for(int i=0;i<n;i++){
scanf("%lf%lf%lf",&r[i],&x[i],&y[i]);
}
slove();
}
}
poj 2932 Coneology (扫描线)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。