CodeForces 934E (Colourful Prospect)[计算几何，欧拉定理]

发表于 | 更新于 | | 阅读次数：

题目链接：http://codeforces.com/problemset/problem/934/E

题目大意：给定平面内n个圆，问这些圆把平面分成了多少个区域。
这题是欧拉定理，但和欧拉定理一般式(V+F-E=2)不太一样..

求圆拆分平面有多少个区域怎么能离得开平面图的欧拉公式呢？
一般平面图欧拉公式：f=e−v+c+1
其中 e 代表边的数量，v 代表点的数量，c 代表连通块的数量，f 代表平面区域的个数
我们把圆弧看作边，交点看作顶点，于是很容易便可以算出 e,v,c 啦~
对于 e ，它相当于每个圆上交点的数量和（因为这些交点把圆拆分成了这么多的弧）
对于 v ，枚举求出交点去重即可
对于 c ，我们已经有了无向图的边，那连通块的数量可以直接 dfs/bfs 或者并查集算出来啦~
然后套用公式就是结果了，注意精度问题。
引用自https://blog.csdn.net/qq_28954601/article/details/79329961

注意圆的欧拉公式中各值的定义也不太一样，E是不会算上单独的圆边的。具体确定方法见上面引用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const double eps=1e-8;
const double inf=1e20;
const double pi=acos(-1.0);
int sgn(double x) {
    if(fabs(x)<eps) return 0;
    if(x<0) return -1;
    else return 1;
}
inline double sqr(double x) { return x*x; }
struct Point {
    double x,y;
    Point() {}
    Point(double _x,double _y) {
        x=_x;
        y=_y;
    }
    double distance(Point p) {
        return hypot(x-p.x,y-p.y);
    }
    double len() {
        return hypot(x,y);
    }
    Point trunc(double r) {
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point(x*r,y*r);
    }
    bool operator ==(Point b) const {
        return sgn(x-b.x)==0 && sgn(y-b.y)==0;
    }
    bool operator <(Point b) const {
        return sgn(x-b.x)==0 ? sgn(y-b.y)<0:x<b.x;
    }
    Point operator -(const Point& b) const {
        return Point(x-b.x,y-b.y);
    }
    Point operator +(const Point& b) const {
        return Point(x+b.x,y+b.y);
    }
    double operator ^(const Point& b) const {
        return x*b.y-y*b.x;
    }
    double operator *(const Point& b) const {
        return x*b.x+y*b.y;
    }
    Point rotleft() {
        return Point(-y,x);
    }
    Point rotright() {
        return Point(y,-x);
    }
};

struct circle {
    Point p;
    double r;
    circle() { }
    circle(Point _p,double _r) {
        p=_p;
        r=_r;
    }
    circle(double x,double y,double _r) {
        p=Point(x,y);
        r=_r;
    }
    int relationcircle(circle v) {
        double d=p.distance(v.p);
        if(sgn(d-r-v.r)>0) return 5;
        if(sgn(d-r-v.r)==0) return 4;
        double l=fabs(r-v.r);
        if(sgn(d-r-v.r)<0 && sgn(d-l)>0) return 3;
        if(sgn(d-l)==0) return 2;
        if(sgn(d-l)<0) return 1;
    }
    int pointcrosscircle(circle v,Point& p1,Point& p2) {
        int rel=relationcircle(v);
        if(rel==1 || rel==5) return 0;
        double d=p.distance(v.p);
        double l=(d*d+r*r-v.r*v.r)/(2*d);
        double h=sqrt(r*r-l*l);
        Point tmp=p+(v.p-p).trunc(l);
        p1=tmp+((v.p-p).rotleft().trunc(h));
        p2=tmp+((v.p-p).rotright().trunc(h));
        if(rel==2 || rel==4)
            return 1;
        return 2;
    }
}cir[4];
Point nodes[20];
int V=0,E=0,C=0;
Point ver[20];
int t=0;
bool innodes(Point x) {
    for(int i=0;i<V;i++)
        if(nodes[i]==x) return 1;
    return 0;
}
bool inver(Point x) {
    for(int i=0;i<t;i++)
        if(ver[i]==x) return 1;
    return 0;
}
int fa[4];
bool vis[4];
int getf(int x) {
    if(fa[x]==x) return x;
    return fa[x]=getf(fa[x]);
}
void merge(int x,int y) {
    int f1=getf(x),f2=getf(y);
    if(f1!=f2) fa[f1]=f2;
}
int main() {
    int n;
    int x,y,r;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d%d%d",&x,&y,&r);
        cir[i]=circle(x,y,r);
    }
    if(n==1) {
        printf("2");
        return 0;
    }
    if(n==2) {
        if(cir[1].relationcircle(cir[2])==3) printf("4");
        else printf("3");
        return 0;
    }
    for(int i=1;i<=3;i++) fa[i]=i;
    Point a,b;
    for(int i=1;i<=3;i++) {
        t=0;
        for(int j=1;j<=3;j++) {
            if(i==j) continue;
            int opt=cir[i].pointcrosscircle(cir[j],a,b);
            if(opt==1) {
                if(!innodes(a)) nodes[V++]=a;
                if(!inver(a)) ver[t++]=a;
                merge(i,j);
            }
            else if(opt==2) {
                if(!innodes(a)) nodes[V++]=a;
                if(!inver(a)) ver[t++]=a;
                if(!innodes(b)) nodes[V++]=b;
                if(!inver(b)) ver[t++]=b;
                merge(i,j);
            }
        }
        E+=t;
    }
    for(int i=1;i<=3;i++) {
        if(!vis[getf(i)]) {
            vis[getf(i)]=true;
            C++;
        }
    }
    printf("%d\n",E-V+C+1);
}