SPOJ 8073 The area of the union of circles （圆并入门）

Sphere Online Judge (SPOJ) - Problem CIRU

【求圆并的若干种算法,圆并扩展算法】_AekdyCoin的空间_百度空间

　　参考AekdyCoin的圆并算法解释，根据理解写出的代码。圆并这么多题中，最基础一题。

　　操作如下：

（1）对一个圆，获得所有与其他圆的交点作为时间戳。

　　a.如果这个圆不被其他任何圆覆盖，这个圆直接保留。

　　b.如果Case中有两个完全重合的圆，可以保留标号小（或大）的圆，也只保留这一个。

（2）每经过一个时间戳就对计数器加减，如果计数器从0变1，加上这段圆弧和对应的三角形。

（3）所有这样的圆独立计算，最后求出的面积累加即可。

代码如下(1y)：

 #include <cmath>

 #include <cstdio>

 #include <cstring>

 #include <iomanip>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const double PI = acos(-1.0);

 const double EPS = 1e-;

 inline int sgn(double x) { return (x > EPS) - (x < -EPS);}

 template<class T> T sqr(T x) { return x * x;}

 typedef pair<double, double> Point;

 #define x first

 #define y second

 Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y);}

 Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);}

 Point operator * (Point a, double p) { return Point(a.x * p, a.y * p);}

 Point operator / (Point a, double p) { return Point(a.x / p, a.y / p);}

 inline double cross(Point a, Point b) { return a.x * b.y - a.y * b.x;}

 inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y;}

 inline double angle(Point a) { return atan2(a.y, a.x);}

 inline double veclen(Point a) { return sqrt(dot(a, a));}

 struct Circle {

     Point c;

     double r;

     Circle() {}

     Circle(Point c, double r) : c(c), r(r) {}

     Point point(double p) { return Point(c.x + r * cos(p), c.y + r * sin(p));}

     void get() { scanf("%lf%lf%lf", &c.x, &c.y, &r);}

 } ;

 bool ccint(Circle a, Circle b, double &a1, double &a2) { // ips for Circle-a (anti-clockwise p1->p2)

     double d = veclen(a.c - b.c);

     double r1 = a.r, r2 = b.r;

     if (sgn(d - r1 - r2) >= ) return ;

     if (sgn(fabs(r1 - r2) - d) >= ) return ;

     double da = acos((sqr(d) + sqr(r1) - sqr(r2)) / ( * d * r1));

     double ang = angle(b.c - a.c);

     a1 = ang - da, a2 = ang + da;

     return ;

 }

 const int N = ;

 Circle cir[N];

 inline double gettri(Point o, Point a, Point b) { return cross(a - o, b - o) / ;}

 inline double getarc(Circle o, double a, double b) { return (b - a) * sqr(o.r) /  - gettri(o.c, o.point(a), o.point(b));}

 typedef pair<double, int> Event;

 Event ev[N << ];

 bool inside(int a, int n) {

     double d, r1, r2;

     for (int i = ; i < n; i++) {

         if (i == a) continue;

         d = veclen(cir[i].c - cir[a].c);

         r1 = cir[i].r, r2 = cir[a].r;

         if (sgn(r1 - r2) ==  && sgn(fabs(r1 - r2) - d) == ) {

             if (i > a) return ;

             continue;

         }

         if (sgn(r1 - r2) >=  && sgn(fabs(r1 - r2) - d) >= ) return ;

     }

     return ;

 }

 double getarea(int a, int n) {

     if (inside(a, n)) return ;

     Circle &c = cir[a];

     double ret = ;

     double a1, a2;

     Point p1, p2;

     int tt = ;

     for (int i = ; i < n; i++) {

         if (i == a) continue;

         if (ccint(c, cir[i], a1, a2)) {

             if (a2 > PI) ev[tt++] = Event(a1, ), ev[tt++] = Event(PI, -), ev[tt++] = Event(-PI, ), ev[tt++] = Event(a2 -  * PI, -);

             else if (a1 < -PI) ev[tt++] = Event(a1 +  * PI, ), ev[tt++] = Event(PI, -), ev[tt++] = Event(-PI, ), ev[tt++] = Event(a2, -);

             else ev[tt++] = Event(a1, ), ev[tt++] = Event(a2, -);

         }

     }

     if (tt == ) return PI * sqr(c.r);

     sort(ev, ev + tt);

     int cnt = ;

     double last = -PI;

     for (int i = ; i < tt; i++) {

         double cur = ev[i].x;

         if (ev[i].y ==  && cnt == ) ret += getarc(c, last, cur) + cross(c.point(last), c.point(cur)) / ;

         cnt += ev[i].y;

         last = cur;

     }

     ret += getarc(c, last, PI) + cross(c.point(last), c.point(PI)) / ;

     return ret;

 }

 double work(int n) {

     double ret = ;

     for (int i = ; i < n; i++) ret += getarea(i, n);

     return ret;

 }

 int main() {

     int n;

     while (~scanf("%d", &n)) {

         for (int i = ; i < n; i++) cir[i].get();

         printf("%.3f\n", work(n));

     }

     return ;

 }

——written by Lyon