POJ-2932题目链接：传送门
A student named Round Square loved to play with cones. He would arrange cones with different base radii arbitrarily on the floor and would admire the intrinsic beauty of the arrangement. The student even began theorizing about how some cones dominate other cones: a cone A dominates another cone B when cone B is completely within the cone A. Furthermore, he noted that there are some cones that not only dominate others, but are themselves dominated, thus creating complex domination relations. After studying the intricate relations of the cones in more depth, the student reached an important conclusion: there exist some cones, all-powerful cones, that have unique properties: an all-powerful cone is not dominated by any other cone. The student became so impressed by the mightiness of the all-powerful cones that he decided to worship these all-powerful cones.
Unfortunately, after having arranged a huge number of cones and having worked hard on developing this grandiose cone theory, the student become quite confused with all these cones, and he now fears that he might worship the wrong cones (what if there is an evil cone that tries to trick the student into worshiping it?). You need to help this student by finding the cones he should worship.
The input le specifies an arrangement of the cones. There are in total N cones (1 ≤ N ≤ 40000). Cone i has radius and height equal to Ri, i = 1 … N. Each cone is hollow on the inside and has no base, so it can be placed over another cone with smaller radius. No two cones touch.
The first line of the input contains the integer N. The next N lines each contain three real numbers Ri, xi, yi separated by spaces, where (xi, yi) are the coordinates of the center of the base of cone i.
The first line of the output le should contain the number of cones that the student should worship. The second line contains the indices of the cones that the student should worship in increasing order. Two consecutive numbers should be separated by a single space.
5 1 0 -2 3 0 3 10 0 0 1 0 1.5 10 50 50
2 3 5
需要注意这是POJ 卡cout和cin，需要用printf和scanf 不能用bits/stdc++.h万能头，需要自己加set,vector等 且需要注意set<pair<>(这中间需要至少一个空格)> ———————————————————————— 平面上有N个两两没有公共点的圆，i号圓的圆心在 ( x i , y i ) (x_i,y_i) (xi,yi),半径为r。求所有最外层的，即不包含于其他圆内部的圆。
预处理各个圆坐标为i，右边为i+n，即按照横坐标x加减半径r的从小到大排序，，按照横坐标x从左到右扫一次，当i＜n时，扫描区域的圆不断增加，且添加且选出符合条件的圆；当i≥n的时候，扫描区域内的圆在减少，需要删除。
//#pragma GCC optimize(2) //#include<bits/stdc++.h> #include<iostream> #include<vector> #include<algorithm> #include<set> using namespace std; #define ll long long #define endl "\n" const int MAX=40012; struct circle{ double x,y,r; }c[MAX]; vector<int>ans; vector<pair<double,int> >p; set<pair<double,int> >st; bool inside(int i,int j){ double tx=c[i].x-c[j].x,ty=c[i].y-c[j].y,tr=c[i].r-c[j].r; return tx*tx+ty*ty<=tr*tr&&c[i].r<=c[j].r; } int main(){ ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0); int n;scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf%lf%lf",&c[i].r,&c[i].x,&c[i].y); p.push_back(make_pair(c[i].x-c[i].r,i)); p.push_back(make_pair(c[i].x+c[i].r,i+n)); } sort(p.begin(),p.end()); for(int i=0;i<p.size();i++){ int id=p[i].second%n; if(p[i].second<n){ set<pair<double,int> >::iterator it=st.lower_bound(make_pair(c[id].y,id)); if(it!=st.end()&&inside(id,it->second))continue; if(it!=st.begin()&&inside(id,(--it)->second))continue; ans.push_back(id); st.insert(make_pair(c[id].y,id)); } else st.erase(make_pair(c[id].y,id)); } sort(ans.begin(),ans.end()); printf("%d\n",ans.size()); for(int i=0;i<ans.size();i++)printf("%d ",ans[i]+1); return 0; }