Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：#
求n个圆的面积并。
思路：#
发现和求2个圆的完全不一样，具体请参考
SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）
（用格林公式搞真是跪烂了。）
没有仔细看细节，当成板子好了（我最菜.jpg）
将代码写成了自己熟悉的风格。
以及双倍经验题：SPOJ VCIRCLES
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月11日 星期三 19时53分30秒
4File Name :ciru.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const double PI = acos(-1.0);
35const int N =1e3+7;
36inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
37struct point
38{
39 double x,y;
40 point(){}
41 point(double x,double y):x(x),y(y){}
42 void input(){scanf("%lf%lf",&x,&y);}
43 double angle(){ return atan2(y,x);}
44 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
45 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
46 point operator * (double t)const{ return point(t*x,t*y);}
47 point operator / (double t)const{ return point(x/t,y/t);}
48 double length() const { return sqrt(x*x+y*y);};
49 point unit()const { double l = length();return point(x/l,y/l); }
50};
51double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
52double dist(const point p1,point p2) { return (p1-p2).length();}
53point rotate(point p,double angle,point o = point(0,0))
54{ point t = p-o;
55 double x = t.x * cos(angle) - t.y*sin(angle);
56 double y = t.y * cos(angle) + t.x*sin(angle);
57 return point (x,y)+o;
58}
59struct region{
60 double st,ed;
61 region(){}
62 region(double st,double ed):st(st),ed(ed){}
63 bool operator < (const region & rhs)const
64 { if (dblcmp(st-rhs.st)) return st<rhs.st;
65 return ed<rhs.ed;
66 }
67};
68struct circle{
69 point c;
70 double r;
71 vector <region>reg;
72 circle(){}
73 circle(point c,double r):c(c),r(r){}
74 void input()
75 {
76 c.input();
77 scanf("%lf",&r);
78 }
79 void add(const region &r){ reg.PB(r);}
80 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
81 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
82};
83double sqr( double x){ return x*x;}
84void intersection(circle cir1,circle cir2,point &p1,point &p2)
85{
86 double l = dist(cir1.c,cir2.c);
87 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
88 double d2 = sqrt(sqr(cir1.r)-sqr(d));
89 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
90 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
91 p1 = mid + v,p2 = mid -v;
92}
93point calc(const circle &cir,double angle)
94{
95 point p = point (cir.c.x+cir.r,cir.c.y);
96 return rotate(p,angle,cir.c);
97}
98
99circle cir[N];
100bool del[N];
101int n;
102
103double solve()
104{
105 double ans = 0 ;
106 for ( int i = 0 ; i < n ; i++){
107 for ( int j = 0 ; j < n ; j++) if (!del[j]){
108 if (i==j) continue;
109 if (cir[j].contain(cir[i]))
110 { del[i] = true;
111 break;
112 }
113 }
114 }
115 for ( int i = 0 ; i < n ; i++) if (!del[i]){
116 circle &mc = cir[i];
117 point p1,p2;
118 bool flag = false;
119 for ( int j = 0 ; j < n ; j++) if (!del[j]){
120 if (i==j) continue;
121 if (!mc.interect(cir[j])) continue;
122 flag = true;
123 intersection(mc,cir[j],p1,p2);
124 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
125 if (dblcmp(rs)<0) rs+=2*PI;
126 if (dblcmp(rt)<0) rt+=2*PI;
127 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
128 else mc.add(region(rs,rt));
129 }
130 if (!flag) { ans += PI*sqr(mc.r); continue;}
131 sort(mc.reg.begin(),mc.reg.end());
132 int cnt = 1;
133 for ( int j = 1 ; j < mc.reg.size() ; j++)
134 {
135 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
136 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
137 else mc.reg[cnt++] = mc.reg[j];
138 }
139 mc.add(region());
140 mc.reg[cnt]=mc.reg[0];
141 for ( int j = 0 ; j < cnt ; j++)
142 {
143 p1 = calc(mc,mc.reg[j].ed);
144 p2 = calc(mc,mc.reg[j+1].st);
145 ans +=cross(p1,p2)/2;
146 double angle = mc.reg[j+1].st - mc.reg[j].ed;
147 if (dblcmp(angle)<0) angle+=2*PI;
148 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
149 }
150 }
151 return ans;
152
153}
154int main()
155{
156 #ifndef ONLINE_JUDGE
157 freopen("./in.txt","r",stdin);
158 #endif
159
160 scanf("%d",&n);
161 for ( int i = 0 ; i < n ; i++) cir[i].input();
162 printf("%.3f\n",solve());
163 #ifndef ONLINE_JUDGE
164 fclose(stdin);
165 #endif
166 return 0;
167}另一个版本：
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月11日 星期三 19时53分30秒
4File Name :ciru.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const double PI = acos(-1.0);
35const int N =1e3+7;
36inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
37struct point
38{
39 double x,y;
40 point(){}
41 point(double x,double y):x(x),y(y){}
42 void input(){scanf("%lf%lf",&x,&y);}
43 double angle(){ return atan2(y,x);}
44 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
45 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
46 point operator * (double t)const{ return point(t*x,t*y);}
47 point operator / (double t)const{ return point(x/t,y/t);}
48 double length() const { return sqrt(x*x+y*y);};
49 point unit()const { double l = length();return point(x/l,y/l); }
50};
51double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
52double dist(const point p1,point p2) { return (p1-p2).length();}
53point rotate(point p,double angle,point o = point(0,0))
54{ point t = p-o;
55 double x = t.x * cos(angle) - t.y*sin(angle);
56 double y = t.y * cos(angle) + t.x*sin(angle);
57 return point (x,y)+o;
58}
59struct region{
60 double st,ed;
61 region(){}
62 region(double st,double ed):st(st),ed(ed){}
63 bool operator < (const region & rhs)const
64 { if (dblcmp(st-rhs.st)) return st<rhs.st;
65 return ed<rhs.ed;
66 }
67};
68struct circle{
69 point c;
70 double r;
71 vector <region>reg;
72 circle(){}
73 circle(point c,double r):c(c),r(r){}
74 void input()
75 {
76 c.input();
77 scanf("%lf",&r);
78 }
79 void add(const region &r){ reg.PB(r);}
80 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
81 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
82};
83double sqr( double x){ return x*x;}
84void intersection(circle cir1,circle cir2,point &p1,point &p2)
85{
86 double l = dist(cir1.c,cir2.c);
87 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
88 double d2 = sqrt(sqr(cir1.r)-sqr(d));
89 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
90 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
91 p1 = mid + v,p2 = mid -v;
92}
93point calc(const circle &cir,double angle)
94{
95 point p = point (cir.c.x+cir.r,cir.c.y);
96 return rotate(p,angle,cir.c);
97}
98
99circle cir[N];
100bool del[N];
101int n;
102
103double solve()
104{
105 double ans = 0 ;
106 for ( int i = 0 ; i < n ; i++){
107 for ( int j = 0 ; j < n ; j++) if (!del[j]){
108 if (i==j) continue;
109 if (cir[j].contain(cir[i]))
110 { del[i] = true;
111 break;
112 }
113 }
114 }
115 for ( int i = 0 ; i < n ; i++) if (!del[i]){
116 circle &mc = cir[i];
117 point p1,p2;
118 bool flag = false;
119 for ( int j = 0 ; j < n ; j++) if (!del[j]){
120 if (i==j) continue;
121 if (!mc.interect(cir[j])) continue;
122 flag = true;
123 intersection(mc,cir[j],p1,p2);
124 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
125 if (dblcmp(rs)<0) rs+=2*PI;
126 if (dblcmp(rt)<0) rt+=2*PI;
127 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
128 else mc.add(region(rs,rt));
129 }
130 if (!flag) { ans += PI*sqr(mc.r); continue;}
131 sort(mc.reg.begin(),mc.reg.end());
132 int cnt = 1;
133 for ( int j = 1 ; j < mc.reg.size() ; j++)
134 {
135 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
136 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
137 else mc.reg[cnt++] = mc.reg[j];
138 }
139 mc.add(region());
140 mc.reg[cnt]=mc.reg[0];
141 for ( int j = 0 ; j < cnt ; j++)
142 {
143 p1 = calc(mc,mc.reg[j].ed);
144 p2 = calc(mc,mc.reg[j+1].st);
145 ans +=cross(p1,p2)/2;
146 double angle = mc.reg[j+1].st - mc.reg[j].ed;
147 if (dblcmp(angle)<0) angle+=2*PI;
148 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
149 }
150 }
151 return ans;
152
153}
154int main()
155{
156 #ifndef ONLINE_JUDGE
157 freopen("./in.txt","r",stdin);
158 #endif
159
160 scanf("%d",&n);
161 for ( int i = 0 ; i < n ; i++) cir[i].input();
162 printf("%.5f\n",solve());
163 #ifndef ONLINE_JUDGE
164 fclose(stdin);
165 #endif
166 return 0;
167}