POJ 2932 Coneology

掃描線

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
typedef pair<double,int> pdi;
typedef struct _cycle{ double x, y; double r;int ind;}cycle;
cycle cs[40005]; int n;
vector<int> okset;
double dist(int a, int b){
double ax  = cs[a].x, ay = cs[a].y;
double bx  = cs[b].x, by = cs[b].y;
return (ax-bx)*(ax-bx) + (ay-by)*(ay-by);
}
int main()
{
scanf("%d", &n);
vector<pdi> xline;
set<pdi> yline;
for(int lx = 0;lx < n;lx++){
scanf("%lf %lf %lf", &cs[lx].r ,&cs[lx].x, &cs[lx].y );
xline.push_back(pdi(cs[lx].x-cs[lx].r, 2*lx));
xline.push_back(pdi(cs[lx].x+cs[lx].r, 2*lx+1));
cs[lx].ind = lx+1;
}
sort(xline.begin(), xline.end());
for(int lx = 0;lx < xline.size();lx++){
int ind = xline[lx].second;
//printf("prc %d\n", ind/2);
int id = ind/2;
if(ind%2 == 0){
set<pdi>::iterator it = yline.lower_bound(pdi(cs[id].y, id));
if(it != yline.end()){
int id2 = it->second;
if(dist(id, id2) <= cs[id2].r*cs[id2].r)
continue;
}
if(it != yline.begin()){
//printf("yy\n");
it--; int id2 = it->second;
if(dist(id, id2)<= cs[id2].r*cs[id2].r)
continue;
}
okset.push_back(cs[id].ind);
yline.insert(pdi(cs[id].y, id));
}else{
yline.erase(pdi(cs[id].y, id));
}
}
sort(okset.begin(), okset.end());
printf("%d\n", okset.size());
for(int lx = 0;lx < okset.size();lx++)
if(lx == okset.size()-1)
printf("%d\n", okset[lx]);
else
printf("%d ", okset[lx]);
return 0;
}