POJ 2932-Coneology（平面扫描-最外层的圆）

逃离我推掉我的手 2022-07-18 00:21 7阅读 0赞

Coneology

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;3827</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;760</td> 
  </tr> 
 </tbody> 
</table>

Description

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.

Input

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*.

Output

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.

Sample Input

5
    1 0 -2
    3 0 3
    10 0 0
    1 0 1.5
    10 50 50

Sample Output

2
    3 5

Source

[MIT Programming Contest 2005][]

## 题目意思： ##

平面上有N个两两木有公共点的圆，给出其半径和圆心的坐标，求所有最外层的，即不包含于其他圆内部的圆。

## 解题思路： ##

平面扫描，当扫描线移动到某个圆的左端，从当前与扫描线相交的最外层的圆中，找到上下两侧y坐标方向距离最近的两个圆，并检查它们就足够了。

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    #include<vector>
    #include<algorithm>
    #include<set>
    #include<queue>
    #include<malloc.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 50000;
    const int INF = 0x3f3f3f3f;
    
    int N;
    double x[maxn],y[maxn],r[maxn];
    bool inside(int i,int j)//判断圆i是否在圆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());//圆的左右两端x的坐标
        //平面扫描
        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':' ');
    }
    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;
    }
    /**
    5
    1 0 -2
    3 0 3
    10 0 0
    1 0 1.5
    10 50 50
    **/

[MIT Programming Contest 2005]: http://poj.org/searchproblem?field=source&key=MIT+Programming+Contest+2005