【题目链接】 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2589
【题目大意】
给出一些圆，问这些圆可以把平面分为几个部分。
【题解】
我们发现圆交图一定是个平面图，因此可以用平面图欧拉公式R=E-V+2
但是我们发现有些圆并不相交，因此每个图需要单独完全计算，
我们计算每个封闭图形的平面数，他们的和+1便是答案，
考虑单独的封闭图形有R=E-V+1，在下图中：
我们发现当蓝色的圆加入图中之后，他为平面增加的点数是4，增加的边数是8，
其中属于蓝色的圆弧的边数为4，其余四条增加的边源于红色和黄色圆弧上点的增加，
所以我们发现对于一个圆来说，它为平面贡献的边数为其与其余圆的交点数，
至于封闭平面图形点的计算，我们在搜索中用set来去重即可。
【代码】
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <set>
using namespace std;
double eps=1e-8;
int sgn(double x) {
if(x<-eps)return -1;
if(x>eps)return 1;
return 0;
}
struct vec{
double x,y;
vec(double x=0,double y=0):x(x),y(y){}
vec operator + (vec v){return vec(x+v.x,y+v.y);}
vec operator - (vec v){return vec(x-v.x,y-v.y);}
vec operator * (double v){return vec(x*v,y*v);}
vec operator / (double v){return vec(x/v,y/v);}
bool operator < (const vec &rhs)const{
if(sgn(x-rhs.x)!=0)return x<rhs.x;
else if(sgn(y-rhs.y)!=0)return y<rhs.y;
else return false;
}
bool operator ==(const vec &rhs)const{
return sgn(x-rhs.x)==0&&sgn(y-rhs.y)==0;
}
double operator *(vec v){return x*v.x+y*v.y;}
double len(){return hypot(x,y);}
double len_sqr(){return x*x+y*y;}
double angle(){return atan2(y,x);}
//逆时针旋转
vec rotate(double c){return vec(x*cos(c)-y*sin(c),x*sin(c)+y*cos(c));}
vec trunc(double l){return (*this)*l/len();}
vec rot90(){return vec(-y,x);}
};
struct circle{
vec c;double r;
circle(vec c=vec(0,0),double r=0):c(c),r(r){}
vec point(const double &a)const{
return vec(c.x+cos(a)*r,c.y+sin(a)*r);
}
};
//圆圆相交
int circle_circle_intersection(circle a,circle b,vec &p1,vec &p2) {
double d=(a.c-b.c).len();
if(sgn(d)==0)return 0;
if(sgn(a.r+b.r-d)<0||sgn(fabs(a.r-b.r)-d)>0)return false;//相离|内含
double an=(b.c-a.c).angle();
double da=acos((a.r*a.r+d*d-b.r*b.r)/(2*a.r*d));
p1=a.point(an-da);
p2=a.point(an+da);
if(p1==p2)return 1;
else return 2;
}
const int N=60;
vector<circle> cir;
vector<int> G[N];
set<vec> dfs_save,set_p[N];
set<vec>::iterator it;
int v[N],E,T,n;
void dfs(int x){
v[x]=1;
for(it=set_p[x].begin();it!=set_p[x].end();it++)dfs_save.insert(*it);
E+=(int)set_p[x].size();
for(int i=0;i<G[x].size();i++)if(!v[G[x][i]])dfs(G[x][i]);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n); cir.clear();
for(int i=0;i<n;i++)G[i].clear(),set_p[i].clear();
memset(v,0,sizeof(v));
for(int i=0;i<n;i++){
double x,y,r;
scanf("%lf%lf%lf",&x,&y,&r);
cir.push_back(circle(vec(x,y),r));
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++){
vec a,b;
int u=circle_circle_intersection(cir[i],cir[j],a,b);
if(u){
G[i].push_back(j); G[j].push_back(i);
set_p[i].insert(a); set_p[j].insert(a);
set_p[i].insert(b); set_p[j].insert(b);
}
}int ans=0;
for(int i=0;i<n;i++){
if(!v[i]){
dfs_save.clear(); E=0;
dfs(i); ans+=E-(int)dfs_save.size()+1;
}
}printf("%d
",ans+1);
}return 0;
}