算法：掃描線
用一條豎直線從左到右掃描所有的圓，處理每個(gè)圓“剛接觸掃描線”和“剛離開(kāi)
掃描線”兩個(gè)事件點(diǎn)。
為了下面描述方便，令某圓A的嵌套層數(shù)為f(A), 如果某圓A被某圓B嵌套且A和B
緊鄰，那么說(shuō)A是B的兒子，B是A的父親。如果圓A，圓B同時(shí)是圓C的兒子，那么A，
B互為兄弟,當(dāng)前考慮的圓為圓C。
根據(jù)“剛接觸掃描線”事件點(diǎn)的上下相鄰事件點(diǎn)分類(lèi)有如下情況：
1）沒(méi)有上方事件點(diǎn)，或者沒(méi)有下方事件點(diǎn)。這時(shí)該圓C的嵌套層數(shù)f(C) = 1
2）上方事件點(diǎn)和下方事件點(diǎn)屬于同一個(gè)圓A，這時(shí)圓A必定是圓C的父親，f(C) =
f(A) + 1
3）上方事件點(diǎn)和下方事件點(diǎn)分別屬于兩個(gè)圓A，B，且f(A) != f(B)，這里不妨
設(shè)f(A) < f(B)，那么A是C的父親，B是C的兄弟。f(C) = f(A) + 1, f(C) = f(B)
4) 上方事件點(diǎn)和下方事件點(diǎn)分別屬于兩個(gè)圓A，B，且f(A) == f(B),那么A是C
的兄弟，B是C的兄弟,f(C) = f(A) = f(B).
在處理“剛接觸掃描線”事件點(diǎn)時(shí)插入一對(duì)點(diǎn)表示該圓與掃描線的相交情況，
并利用上述分類(lèi)計(jì)算其嵌套層數(shù)，在處理“ 剛離開(kāi)掃描線”事件點(diǎn)是刪除對(duì)應(yīng)
的那一對(duì)點(diǎn)。可以采用STL 中的set來(lái)維護(hù)
相關(guān)的題目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=2932
http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4125
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <set>
#include <algorithm>
using namespace std;
const int UP = 0;
const int DOWN = 1;
const int IN = 0;
const int OUT = 1;
const int N = 50005;
int Time;
struct circle {
int x, y, r;
int w;
void read() {
scanf("%d %d %d", &x, &y, &r);
w = 0;
}
int getX(int flag) {
if( flag == IN ) return x - r;
else return x + r;
}
double getY(int flag) {
double ret = sqrt((double)r*r-(double)(Time-x)*(Time-x));
if( flag == UP ) return (double)y + ret;
else return (double)y - ret;
}
} cir[N];
struct event {
int x, y, id;
int flag;
void get(int _x, int _y, int _id, int _flag) {
x = _x;
y = _y;
id = _id;
flag = _flag;
}
bool operator<(const event ev) const {
return x < ev.x || x == ev.x && y > ev.y;
}
} eve[N*2];
struct node {
int id;
int flag;
node(){}
node(int _id, int _flag) {
id = _id;
flag = _flag;
}
bool operator<(const node a) const {
double y1 = cir[id].getY(flag);
double y2 = cir[a.id].getY(a.flag);
return y1 > y2 || y1 == y2 && flag < a.flag;
}
};
int n, eveN;
set<node> line;
set<node>::iterator it, f, e, p;
inline int max(int a, int b) { return a > b ? a : b;}
void moveline() {
line.clear();
for(int i = 0; i < eveN; i ++) {
Time = eve[i].x;
if( eve[i].flag == OUT ) {
line.erase(node(eve[i].id, UP));
line.erase(node(eve[i].id, DOWN));
} else {
it = line.insert(node(eve[i].id, UP)).first;
e = f = it;
e ++;
int id = it->id;
if( it == line.begin() || e == line.end() ) {
cir[id].w = 1;
} else {
f --;
if( f->id == e->id ) {
cir[id].w = cir[f->id].w + 1;
} else {
cir[id].w = max( cir[f->id].w, cir[e->id].w);
}
}
line.insert(node(eve[i].id, DOWN));
}
}
}
int main() {
while( scanf("%d", &n) != EOF ) {
eveN = 0;
for(int i = 0; i < n; i ++) {
cir[i].read();
eve[eveN++].get(cir[i].getX(IN), cir[i].y, i, IN);
eve[eveN++].get(cir[i].getX(OUT), cir[i].y, i, OUT);
}
sort(eve, eve + eveN);
moveline();
int ans = 0;
for(int i = 0; i < n; i ++) {
ans = max(ans, cir[i].w);
}
printf("%d\n", ans);
}
}