ZOJ 2589 Circles（平面图欧拉公式）

【题目链接】 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\n",ans+1);

    }return 0;

}