hdu 3511 Prison Break 圓 掃描線

Prison Break

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 1850    Accepted Submission(s): 563

Problem Description To save Sara, Michael Scofield was captured by evil policemen and he was arrested in Prison again. As is known to all, nothing can stop Michael, so Prison Break continues.

The prison consists of many circular walls. These walls won't intersect or tangent to each other. 

Now Michael is arrested in one of the deepest rooms, and he wants to know how many walls he has to break at least for running out. In figure 1, Michael has to break 3 walls at least and in figure 2, 2 walls are needed.  

Input There will be multiple test cases (no more than 10) in a test data.

For each test case, the first line contains one number: n (1<=n<=50,000) indicating the total number of circular walls.

Then n lines follow, each line contains three integers x, y, r. (x,y) indicates the center of circular wall and r indicates the radius of the wall.

-100,000<=x,y<=100,000 

1 <= r <= 100,000

The input ends up with EOF.

Output The least number of walls to break for running out.  

Sample Input

3
0 0 1
0 0 2
0 0 3
3
0 0 10
5 0 1
-5 0 1
        

Sample Output

3
2
        

Source 2010 ACM-ICPC Multi-University Training Contest（8）——Host by ECNU

題意：

    給出很多個圓，沒有相切，相交，隻有相容和相離的情況。求一個圓被其他圓包圍的個數，最多是多少？就是求圓的深度。

方法：

    掃描線的方法是N*long(N)的

     假設圓是按照圓心的x坐标排序的。有一條掃描線x = z 會與很多圓相交于兩個點，分别對應于這個圓的上半圓和下半圓。交點從上到下是順序的，當掃描線繼續向前移動的時候，這種相對順序是不會改變的。此時如果再加入新的掃描線與其他圓的交點情況，隻要把掃描線x代入每個圓中，計算得到y的坐标，然後在這個位置上插入該點即可。

用線性的資料結構是比較難以實作的，因為交點的y坐标會改變。但是如果采用的是樹形結構，那麼容易了解，樹上的結點的相對順序不會改變。插入一個點的時候，隻要比較兩個結點目前的大小，就可以在一個位置上插入該點了。

       STL中的set其實也是個樹形結構，隻需要對比較函數做一些修改就可以實作了。

方法：

        STL結點記錄的圓的id資訊，以及在比較函數中，計算的y是對應是圓的上部分還是下部分。修改比較函數的輸入是（id，ty）

        定義全局變量globalx 表示掃描線目前的x坐标。 把globalx代入方程求得掃描線與圓id的交點，如果ty=1取上半圓的交點。

       通過計算得到y1，y2再比較大小即可。 因為圓不想交，對于任何一個globalx的值，除了id值一樣外，不能得到y1，y2的值是一樣的。是以id一樣時，判斷ty的大小即可。

掃描線的掃描順序是x從大到小。首先将圓的左頂點和右頂點加入數組中，然後對這個數組進行排序，就是掃描線的前進取值方式了。

對于一個點，如果是左頂點，則加入點（id，1）到set中，然後檢視這個點上方和下方的點情況：

       1.    上下點屬于同一個圓，那麼該圓就是目前圓的直接包含的圓了

       2.  沒有上面的點，或者沒有下面的點，說明這個圓是最外圍的圓

      3.  上下點屬于不同的圓，那麼深度大的那個圓就是目前圓的兄弟，另一個便是目前圓的直接包含圓了

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
#define maxn 100010
struct Circle{
    int id,x,r,y;
    Circle(int _id=0,int _x=0,int _y=0){
        id=_id, x=_x, y=_y;
    }
};
Circle cir[maxn];
//用于對圓的左右端點排序
Circle p[maxn];
int cmp(Circle a,Circle b){
    return a.x < b.x;
}
//用于掃面的位置排序，globalx是目前掃描線的位置
int globalx;

//記錄掃描線的交點資訊ty = 1表示上交點
struct Point{
    int id,ty;
    Point(int _id=0,int _ty=0){
        id = _id;
        ty = _ty;
    }
};
//計算圓id在x=globalx時的y坐标
double yposition(int id,int ty){
    double x = globalx - cir[id].x;
    double y = sqrt(cir[id].r*1.0*cir[id].r-x*x);
    if(ty == 1) return y+cir[id].y;
    return cir[id].y-y;
}
//掃描線與圓的交點按y從大到小排序
bool operator < ( Point a, Point  b) {
    if(a.id == b.id)
        return a.ty > b.ty;
    return  yposition(a.id,a.ty) > yposition(b.id,b.ty);
}

set<Point> haha;
int fa[maxn];
int dep[maxn];

int main(){
    int n,f;
    while(scanf("%d",&n)!=EOF){
        for(int i = 0;i < n; i++){
            scanf("%d%d%d",&cir[i].x,&cir[i].y,&cir[i].r);
            p[i*2]   = Circle(i,cir[i].x-cir[i].r,0);
            p[i*2+1] = Circle(i,cir[i].x+cir[i].r,1);
        }
        int nn = 2 * n;
        sort(p,p+nn,cmp);
        haha.clear();
        set<Point>::iterator it1,it2;
        memset(dep,0,sizeof(dep));
        int ans = 0;
        for(int i = 0;i < nn; i++){
            globalx = p[i].x;
            if(p[i].y == 1){
                haha.erase(Point(p[i].id,0));
                haha.erase(Point(p[i].id,1));
            }
            else {
                it1 = haha.insert(Point(p[i].id,1)).first;
                it2 = it1;
                it1++;
                if(it1 == haha.end() || it2 == haha.begin()){
                    //fa[p[i].id] = f =n;
                    dep[p[i].id] = 1;
                }
                else {
                    it2--;
                    if(it2->id == it1->id){
                        dep[p[i].id] = dep[it1->id]+1;
                    }
                    else
                        dep[p[i].id] = max(dep[it2->id],dep[it1->id]);
                }
                haha.insert(Point(p[i].id,0));
            }
            ans = max(ans,dep[p[i].id]);
        }
        printf("%d\n",ans);
    }
    return 0;
}

/*
3
0 0 1
0 0 2
0 0 3
3
0 0 10
5 0 1
-5 0 1
3
0 0 100
80 80 10
88 88 1
5
0 0 100
0 1 1
0 4 1
0 9 1
3 0 1

*/