SPOJ CIRUT - CIRU2 (多个圆交，求交任意次的面积，模板题)
题意&思路：
给出n个圆
求恰好k个圆相交的面积，k属于1..n
先放个别人的代码。。。
我真是体会到了。。。软件工程这门课的重要性。。。
这代码真是烂得印象深刻。。。几何题全是面向过程？
circle和point 类写在一起。。。感觉所有糟糕的写法这份代码全都占了。。。
/* ***********************************************
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))
19#define pi pair < int ,int >
20#define MP make_pair
using namespace std;
1typedef long long LL;
2typedef unsigned long long ULL;
3typedef vector <int> VI;
4const int INF = 0x3f3f3f3f;
5const double eps = 1e-10;
6const int MOD = 100000007;
7const int MAXN = 1E3+7;
8const double PI = acos(-1.0);
9#define sqr(x) ((x)*(x))
10const int N = 1010;
11double area[N];
12int n;
1int dcmp(double x)
2{
3 if (x < -eps) return -1;
4 else return x > eps;
5}
1struct cp
2{
3 double x, y, r, angle;
4 int d;
5 cp() {}
6 cp(double xx, double yy, double ang = 0, int t = 0)
7 {
8 x = xx;
9 y = yy;
10 angle = ang;
11 d = t;
12 }
13 void get()
14 {
15 scanf("%lf%lf%lf", &x, &y, &r);
16 d = 1;
17 }
18} cir[N], tp[N * 2];
1double dis(cp a, cp b)
2{
3 return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
4}
1double cross(cp p0, cp p1, cp p2)
2{
3 return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
4}
1int CirCrossCir(cp p1, double r1, cp p2, double r2, cp &cp1, cp &cp2)
2{
3 double mx = p2.x - p1.x, sx = p2.x + p1.x, mx2 = mx * mx;
4 double my = p2.y - p1.y, sy = p2.y + p1.y, my2 = my * my;
5 double sq = mx2 + my2, d = -(sq - sqr(r1 - r2)) * (sq - sqr(r1 + r2));
6 if (d + eps < 0) return 0;
7 if (d < eps) d = 0;
8 else d = sqrt(d);
9 double x = mx * ((r1 + r2) * (r1 - r2) + mx * sx) + sx * my2;
10 double y = my * ((r1 + r2) * (r1 - r2) + my * sy) + sy * mx2;
11 double dx = mx * d, dy = my * d;
12 sq *= 2;
13 cp1.x = (x - dy) / sq;
14 cp1.y = (y + dx) / sq;
15 cp2.x = (x + dy) / sq;
16 cp2.y = (y - dx) / sq;
17 if (d > eps) return 2;
18 else return 1;
19}
1bool circmp(const cp& u, const cp& v)
2{
3 return dcmp(u.r - v.r) < 0;
4}
1bool cmp(const cp& u, const cp& v)
2{
3 if (dcmp(u.angle - v.angle)) return u.angle < v.angle;
4 return u.d > v.d;
5}
1double calc(cp cir, cp cp1, cp cp2)
2{
3 double ans = (cp2.angle - cp1.angle) * sqr(cir.r)
4 - cross(cir, cp1, cp2) + cross(cp(0, 0), cp1, cp2);
5 return ans / 2;
6}
1void CirUnion(cp cir[], int n)
2{
3 cp cp1, cp2;
4 sort(cir, cir + n, circmp);
5 for (int i = 0; i < n; ++i)
6 for (int j = i + 1; j < n; ++j)
7 if (dcmp(dis(cir[i], cir[j]) + cir[i].r - cir[j].r) <= 0)
8 cir[i].d++;
9 for (int i = 0; i < n; ++i)
10 {
11 int tn = 0, cnt = 0;
12 for (int j = 0; j < n; ++j)
13 {
14 if (i == j) continue;
15 if (CirCrossCir(cir[i], cir[i].r, cir[j], cir[j].r,
16 cp2, cp1) < 2) continue;
17 cp1.angle = atan2(cp1.y - cir[i].y, cp1.x - cir[i].x);
18 cp2.angle = atan2(cp2.y - cir[i].y, cp2.x - cir[i].x);
19 cp1.d = 1;
20 tp[tn++] = cp1;
21 cp2.d = -1;
22 tp[tn++] = cp2;
23 if (dcmp(cp1.angle - cp2.angle) > 0) cnt++;
24 }
25 tp[tn++] = cp(cir[i].x - cir[i].r, cir[i].y, PI, -cnt);
26 tp[tn++] = cp(cir[i].x - cir[i].r, cir[i].y, -PI, cnt);
27 sort(tp, tp + tn, cmp);
28 int p, s = cir[i].d + tp[0].d;
29 for (int j = 1; j < tn; ++j)
30 {
31 p = s;
32 s += tp[j].d;
33 area[p] += calc(cir[i], tp[j - 1], tp[j]);
34 }
35 }
36}
1void solve()
2{
3 scanf("%d", &n);
4 for (int i = 0; i < n; ++i)
5 cir[i].get();
6 memset(area, 0, sizeof(area));
7 CirUnion(cir, n);
8 //去掉重复计算的
9 for (int i = 1; i <= n; ++i)
10 {
11 area[i] -= area[i + 1];
12 }
13 //area[i]为重叠了i次的面积
14 for ( int i = 1 ; i <= n ; i++) printf("[%d] = %.3f\n",i,area[i]+eps);
15 //tot 为总面积
16 //double tot = 0;
17 //for(int i=1; i<=n; i++) tot += area[i];
18 //printf("%f\n", tot);
19}
1int main()
2{
3 // freopen("./in.txt", "r", stdin);
4 solve();
5 return 0;
6}
打算改写一下。。。这代码实在是。。烂得看不下去了。。。
所以说。。。读别人代码。。。才能体会到代码风格的重要性啊。。。orz
重构了代码，感觉清爽了很多。。
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.circlep
************************************************ */
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))
19#define pi pair < int ,int >
20#define MP make_pair
21using namespace std;
22typedef long long LL;
23typedef unsigned long long ULL;
24typedef vector <int> VI;
25const int INF = 0x3f3f3f3f;
26const double eps = 1e-10;
27const int MAXN = 1E3+7;
28const double PI = acos(-1.0);
29#define sqr(x) ((x)*(x))
30const int N = 1010;
31double area[N];
32int n;
1int dblcmp(double d){ return d<-eps?-1:d>eps;}
2struct point
3{
4 double x,y;
5 double ang;
6 int d;
7 point(){}
8 point(double x,double y):x(x),y(y){}
9 point(double _x,double _y,double _ang,int _d)
10 {
11 x = _x;
12 y = _y;
13 ang = _ang;
14 d = _d;
15 }
16 void input(){scanf("%lf%lf",&x,&y);}
17 double angle(){ return atan2(y,x);}
18 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
19 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
20 point operator * (double t)const{ return point(t*x,t*y);}
21 point operator / (double t)const{ return point(x/t,y/t);}
22 double length() const { return sqrt(x*x+y*y);};
23 point unit()const { double l = length();return point(x/l,y/l); }
24}tp[N*2];
25double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
26double dist(const point p1,point p2) { return (p1-p2).length();}
27struct circle
28{
29 point c;
30 double r;
31 int d;
32 void input()
33 {
34 c.input();
35 scanf("%lf",&r);
36 d = 1;
37 }
38 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
39 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
40} cir[N];// tp[N * 2];
1double dis(point a, point b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));}
2int CirCrossCir(circle cir1,circle cir2, point &p1, point &p2)
3{
4 point m = cir2.c-cir1.c;
5 point s = cir2.c+cir1.c;
6 point m2 = point(sqr(m.x),sqr(m.y));
7 double dis2 = m2.x + m2.y, d = -(dis2 - sqr(cir1.r - cir2.r)) * (dis2 - sqr(cir1.r + cir2.r));
8 if (d + eps < 0) return 0;
9 if (d < eps) d = 0;
10 else d = sqrt(d);
11 double x = m.x * ((cir1.r + cir2.r) * (cir1.r - cir2.r) + m.x * s.x) + s.x * m2.y;
12 double y = m.y * ((cir1.r+ cir2.r) * (cir1.r - cir2.r) + m.y * s.y) + s.y * m2.x;
13 point dp = m*d;
14 dis2 *= 2;
15 p1 = point (x-dp.y,y+dp.x)/dis2;
16 p2 = point (x+dp.y,y-dp.x)/dis2;
17 if (d > eps) return 2;
18 else return 1;
19}
20bool circmp(const circle& u, const circle& v)
21{
22 return dblcmp(u.r - v.r) < 0;
23}
24bool cmp(const point& u, const point& v)
25{
26 if (dblcmp(u.ang - v.ang)) return u.ang < v.ang;
27 return u.d > v.d;
28}
1double calc(circle cir, point p1, point p2)
2{
3 double ans = (p2.ang - p1.ang) * sqr(cir.r)
4 - cross ( (p1-cir.c),(p2-cir.c)) + cross( p1,p2);
5 return ans *0.5;
6}
1void CirUnion(circle cir[], int n)
2{
3 circle cir1, cir2;
4 point p1,p2;
5 sort(cir, cir + n, circmp);
6 for (int i = 0; i < n; ++i)
7 for (int j = i + 1; j < n; ++j)
8 if (cir[j].contain(cir[i]))
9 cir[i].d++;
10 for (int i = 0; i < n; ++i)
11 {
12 int tn = 0, cnt = 0;
13 for (int j = 0; j < n; ++j)
14 {
15 if (i == j) continue;
16 if (CirCrossCir(cir[i],cir[j],p2, p1) < 2) continue;
17 p1.ang = (p1-cir[i].c).angle();
18 p2.ang = (p2-cir[i].c).angle();
19 p1.d = 1;
20 tp[tn++] = p1;
21 p2.d = -1;
22 tp[tn++] = p2;
23 if (dblcmp(p1.ang - p2.ang) > 0) cnt++;
24 }
25 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, PI, -cnt);
26 tp[tn++] = point(cir[i].c.x - cir[i].r, cir[i].c.y, -PI, cnt);
27 sort(tp, tp + tn, cmp);
28 int p, s = cir[i].d + tp[0].d;
29 for (int j = 1; j < tn; ++j)
30 {
31 p = s;
32 s += tp[j].d;
33 area[p] += calc(cir[i], tp[j - 1], tp[j]);
34 }
35 }
36}
37void solve()
38{
39 scanf("%d", &n);
40 for (int i = 0; i < n; ++i)
41 cir[i].input();
42 memset(area, 0, sizeof(area));
43 CirUnion(cir, n);
44 //去掉重复计算的
45 for (int i = 1; i <= n; ++i)
46 {
47 area[i] -= area[i + 1];
48 }
49 //area[i]为重叠了i次的面积
50 for ( int i = 1 ; i <= n ; i++) printf("[%d] = %.3f\n",i,area[i]+eps);
51 //tot 为总面积
52 //double tot = 0;
53 //for(int i=1; i<=n; i++) tot += area[i];
54 //printf("%f\n", tot);
55}
1int main()
2{
3 // freopen("./in.txt", "r", stdin);
4 solve();
5 return 0;
6}