记录编号	120316	评测结果	AAAAAAA
题目名称	[POJ1688]海豚池	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.032 s
提交时间	2014-09-16 11:43:18	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
#define sqr(x) ((x)*(x))
const int SIZE=1010;
const double eps=1e-18,jitter=1e-9,pi=acos(-1.0),INF=5000;
int N;
class CIRCLE{
public:
	double x,y,r;
	void print(void){
		cout<<"("<<x<<" "<<y<<")"<<" "<<r<<endl;
	}
}C[SIZE];
bool cut(CIRCLE c,double h,double &l,double &r){//切直线y=h
	if(fabs(c.y-h)>=c.r-eps) return false;
	double delta=sqrt(sqr(c.r)-sqr(c.y-h));
	l=c.x-delta,r=c.x+delta;
	return true;
}
bool qua_solve(double a,double b,double c,double &x1,double &x2){
	double delta=(b*b-4.0*a*c);
	if(delta<0) return false;
	x1=(-b+sqrt(delta))/(a*2.0),x2=(-b-sqrt(delta))/(a*2.0);
	return true;
}
bool cross(CIRCLE s,CIRCLE t,double &y1,double &y2){
	if(sqrt(sqr(s.x-t.x)+sqr(s.y-t.y))>s.r+t.r) return false;
	double a=2.0*(s.x-t.x),b=2.0*(s.y-t.y);
	double c=sqr(s.r)-sqr(t.r)-sqr(s.x)+sqr(t.x)-sqr(s.y)+sqr(t.y);
	if(fabs(a)<eps){
		y1=y2=-c/b;
		return true;
	}
	return qua_solve(sqr(b)/sqr(a)+1.0,2.0*b*c/sqr(a)+2.0*b*s.x/a-2.0*s.y,sqr(c)/sqr(a)+2.0*c*s.x/a+sqr(s.x)+sqr(s.y)-sqr(s.r),y1,y2);
}
class PR{
public:
	double l,r;
};
void print(PR a){
	cout<<"["<<a.l<<" "<<a.r<<"]";
}
bool operator < (PR a,PR b){
	if(a.r==b.r) return a.l<b.l;
	return a.r<b.r;
}
bool cross(PR a,PR b){
	if(b<a) swap(a,b);
	return b.l<a.r;
}
bool del[SIZE]={0};
PR s[SIZE];
void make_cut(PR out[SIZE],int &ot,double h){
	int tot=0;
	double l,r;
	for(int i=1;i<=N;i++)
		if(cut(C[i],h,l,r)) s[++tot]=(PR){l,r};
	sort(s+1,s+1+tot);
	memset(del,0,sizeof(del));
	for(int i=1;i<=tot;i++){
		for(int j=1;j<i;j++){
			if(del[j]) continue;
			if(s[i].l<s[j].r){
				s[i].l=min(s[i].l,s[j].l);
				del[j]=true;
			}
		}
	}
	int tt=0;
	for(int i=1;i<=tot;i++) if(!del[i]) s[++tt]=s[i];
	tot=tt;
	ot=0;
	s[0].r=-INF,s[tot+1].l=INF;
	for(int i=0;i<=tot;i++)
		if(s[i+1].l-s[i].r>eps) out[++ot]=(PR){s[i].r,s[i+1].l};
}
PR seg[2][SIZE];
int tot[2];
bool exi[SIZE];//在更上面一行有交叉的区间(即继承了它的区间)
int belong[2][SIZE];
vector<double> event;
vector<double> e;
int ans=0;
void addevt(double x){e.push_back(x);}
void make_event(void){
	for(int i=1;i<=N;i++) addevt(C[i].y-C[i].r),addevt(C[i].y+C[i].r);
	double h1,h2;
	for(int i=1;i<=N;i++)
		for(int j=i+1;j<=N;j++)
			if(cross(C[i],C[j],h1,h2))
				addevt(h1),addevt(h2);
	sort(e.begin(),e.end());
	for(int i=0;i<e.size();i++) if(!i||e[i]>e[i-1]+jitter*2.0) event.push_back(e[i]);
}
void scan(void){
	int bnum=1;
	tot[0]=1;
	belong[0][1]=1;
	for(int t=0;t<event.size();t++){
		memset(exi,0,sizeof(exi));
		memset(belong[1],0,sizeof(belong[1]));
		make_cut(seg[0],tot[0],event[t]-jitter);
		make_cut(seg[1],tot[1],event[t]+jitter);
		for(int i=1;i<=tot[0];i++){
			for(int j=1;j<=tot[1];j++){
				if(cross(seg[0][i],seg[1][j])){
					belong[1][j]=belong[0][i];
					exi[belong[0][i]]=true;
				}
			}
		}
		for(int i=1;i<=tot[0];i++){
			if(!exi[belong[0][i]]){
				ans++;
				exi[belong[0][i]]=true;
			}
		}
		for(int i=1;i<=tot[1];i++) if(!belong[1][i]) belong[1][i]=++bnum;
		memcpy(belong[0],belong[1],sizeof(belong[0]));
	}
}
void work(void){
	make_event();
	scan();
	printf("%d\n",ans);
}
void read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%lf%lf%lf",&C[i].x,&C[i].y,&C[i].r);
}
int main(){
	freopen("dolphinpool.in","r",stdin);
	freopen("dolphinpool.out","w",stdout);
	read();
	work();
	return 0;
}