spoj CIRU - The area of the union of circles (多个圆面积并，模板题)
题意：
多n个圆的面积并。
思路：
发现和求2个圆的完全不一样，具体请参考
SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）
（用格林公式搞真是跪烂了。。。。
没有仔细看细节，当成板子好了(我最菜.jpg
将代码写成了自己熟悉的风格。
以及双倍经验题:SPOJ VCIRCLES
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const double PI = acos(-1.0);
7const int N =1e3+7;
8inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
9struct point
10{
11 double x,y;
12 point(){}
13 point(double x,double y):x(x),y(y){}
14 void input(){scanf("%lf%lf",&x,&y);}
15 double angle(){ return atan2(y,x);}
16 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
17 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
18 point operator * (double t)const{ return point(t*x,t*y);}
19 point operator / (double t)const{ return point(x/t,y/t);}
20 double length() const { return sqrt(x*x+y*y);};
21 point unit()const { double l = length();return point(x/l,y/l); }
22};
23double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
24double dist(const point p1,point p2) { return (p1-p2).length();}
25point rotate(point p,double angle,point o = point(0,0))
26{ point t = p-o;
27 double x = t.x * cos(angle) - t.y*sin(angle);
28 double y = t.y * cos(angle) + t.x*sin(angle);
29 return point (x,y)+o;
30}
31struct region{
32 double st,ed;
33 region(){}
34 region(double st,double ed):st(st),ed(ed){}
35 bool operator < (const region & rhs)const
36 { if (dblcmp(st-rhs.st)) return st<rhs.st;
37 return ed<rhs.ed;
38 }
39};
40struct circle{
41 point c;
42 double r;
43 vector <region>reg;
44 circle(){}
45 circle(point c,double r):c(c),r(r){}
46 void input()
47 {
48 c.input();
49 scanf("%lf",&r);
50 }
51 void add(const region &r){ reg.PB(r);}
52 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
53 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
54};
55double sqr( double x){ return x*x;}
56void intersection(circle cir1,circle cir2,point &p1,point &p2)
57{
58 double l = dist(cir1.c,cir2.c);
59 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
60 double d2 = sqrt(sqr(cir1.r)-sqr(d));
61 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
62 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
63 p1 = mid + v,p2 = mid -v;
64}
65point calc(const circle &cir,double angle)
66{
67 point p = point (cir.c.x+cir.r,cir.c.y);
68 return rotate(p,angle,cir.c);
69}
1circle cir[N];
2bool del[N];
3int n;
1double solve()
2{
3 double ans = 0 ;
4 for ( int i = 0 ; i < n ; i++){
5 for ( int j = 0 ; j < n ; j++) if (!del[j]){
6 if (i==j) continue;
7 if (cir[j].contain(cir[i]))
8 { del[i] = true;
9 break;
10 }
11 }
12 }
13 for ( int i = 0 ; i < n ; i++) if (!del[i]){
14 circle &mc = cir[i];
15 point p1,p2;
16 bool flag = false;
17 for ( int j = 0 ; j < n ; j++) if (!del[j]){
18 if (i==j) continue;
19 if (!mc.interect(cir[j])) continue;
20 flag = true;
21 intersection(mc,cir[j],p1,p2);
22 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
23 if (dblcmp(rs)<0) rs+=2*PI;
24 if (dblcmp(rt)<0) rt+=2*PI;
25 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
26 else mc.add(region(rs,rt));
27 }
28 if (!flag) { ans += PI*sqr(mc.r); continue;}
29 sort(mc.reg.begin(),mc.reg.end());
30 int cnt = 1;
31 for ( int j = 1 ; j < mc.reg.size() ; j++)
32 {
33 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
34 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
35 else mc.reg[cnt++] = mc.reg[j];
36 }
37 mc.add(region());
38 mc.reg[cnt]=mc.reg[0];
39 for ( int j = 0 ; j < cnt ; j++)
40 {
41 p1 = calc(mc,mc.reg[j].ed);
42 p2 = calc(mc,mc.reg[j+1].st);
43 ans +=cross(p1,p2)/2;
44 double angle = mc.reg[j+1].st - mc.reg[j].ed;
45 if (dblcmp(angle)<0) angle+=2*PI;
46 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
47 }
48 }
49 return ans;
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("./in.txt","r",stdin);
6 #endif
1 scanf("%d",&n);
2 for ( int i = 0 ; i < n ; i++) cir[i].input();
3 printf("%.3f\n",solve());
4 #ifndef ONLINE_JUDGE
5 fclose(stdin);
6 #endif
7 return 0;
8}
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const double PI = acos(-1.0);
7const int N =1e3+7;
8inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
9struct point
10{
11 double x,y;
12 point(){}
13 point(double x,double y):x(x),y(y){}
14 void input(){scanf("%lf%lf",&x,&y);}
15 double angle(){ return atan2(y,x);}
16 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
17 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
18 point operator * (double t)const{ return point(t*x,t*y);}
19 point operator / (double t)const{ return point(x/t,y/t);}
20 double length() const { return sqrt(x*x+y*y);};
21 point unit()const { double l = length();return point(x/l,y/l); }
22};
23double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
24double dist(const point p1,point p2) { return (p1-p2).length();}
25point rotate(point p,double angle,point o = point(0,0))
26{ point t = p-o;
27 double x = t.x * cos(angle) - t.y*sin(angle);
28 double y = t.y * cos(angle) + t.x*sin(angle);
29 return point (x,y)+o;
30}
31struct region{
32 double st,ed;
33 region(){}
34 region(double st,double ed):st(st),ed(ed){}
35 bool operator < (const region & rhs)const
36 { if (dblcmp(st-rhs.st)) return st<rhs.st;
37 return ed<rhs.ed;
38 }
39};
40struct circle{
41 point c;
42 double r;
43 vector <region>reg;
44 circle(){}
45 circle(point c,double r):c(c),r(r){}
46 void input()
47 {
48 c.input();
49 scanf("%lf",&r);
50 }
51 void add(const region &r){ reg.PB(r);}
52 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
53 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
54};
55double sqr( double x){ return x*x;}
56void intersection(circle cir1,circle cir2,point &p1,point &p2)
57{
58 double l = dist(cir1.c,cir2.c);
59 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
60 double d2 = sqrt(sqr(cir1.r)-sqr(d));
61 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
62 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
63 p1 = mid + v,p2 = mid -v;
64}
65point calc(const circle &cir,double angle)
66{
67 point p = point (cir.c.x+cir.r,cir.c.y);
68 return rotate(p,angle,cir.c);
69}
1circle cir[N];
2bool del[N];
3int n;
1double solve()
2{
3 double ans = 0 ;
4 for ( int i = 0 ; i < n ; i++){
5 for ( int j = 0 ; j < n ; j++) if (!del[j]){
6 if (i==j) continue;
7 if (cir[j].contain(cir[i]))
8 { del[i] = true;
9 break;
10 }
11 }
12 }
13 for ( int i = 0 ; i < n ; i++) if (!del[i]){
14 circle &mc = cir[i];
15 point p1,p2;
16 bool flag = false;
17 for ( int j = 0 ; j < n ; j++) if (!del[j]){
18 if (i==j) continue;
19 if (!mc.interect(cir[j])) continue;
20 flag = true;
21 intersection(mc,cir[j],p1,p2);
22 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
23 if (dblcmp(rs)<0) rs+=2*PI;
24 if (dblcmp(rt)<0) rt+=2*PI;
25 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
26 else mc.add(region(rs,rt));
27 }
28 if (!flag) { ans += PI*sqr(mc.r); continue;}
29 sort(mc.reg.begin(),mc.reg.end());
30 int cnt = 1;
31 for ( int j = 1 ; j < mc.reg.size() ; j++)
32 {
33 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
34 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
35 else mc.reg[cnt++] = mc.reg[j];
36 }
37 mc.add(region());
38 mc.reg[cnt]=mc.reg[0];
39 for ( int j = 0 ; j < cnt ; j++)
40 {
41 p1 = calc(mc,mc.reg[j].ed);
42 p2 = calc(mc,mc.reg[j+1].st);
43 ans +=cross(p1,p2)/2;
44 double angle = mc.reg[j+1].st - mc.reg[j].ed;
45 if (dblcmp(angle)<0) angle+=2*PI;
46 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
47 }
48 }
49 return ans;
1}
2int main()
3{
4 #ifndef ONLINE_JUDGE
5 freopen("./in.txt","r",stdin);
6 #endif
1 scanf("%d",&n);
2 for ( int i = 0 ; i < n ; i++) cir[i].input();
3 printf("%.5f\n",solve());
4 #ifndef ONLINE_JUDGE
5 fclose(stdin);
6 #endif
7 return 0;
8}