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}