fork(1) download
copy 
  1. #include <algorithm>
  2. #include <cstdio>
  3. #include <sstream>
  4. #include <cstdlib>
  5. #include <cctype>
  6. #include <cmath>
  7. #include <set>
  8. #include <queue>
  9. #include <stack>
  10. #include <list>
  11. #include <iostream>
  12. #include <fstream>
  13. #include <numeric>
  14. #include <string>
  15. #include <vector>
  16. #include <cstring>
  17. #include <map>
  18. #include <iterator>
  19. #include <deque>
  20. #include <climits>
  21. #include <complex>
  22. #include <bitset>
  23. #include <limits>
  24.  
  25. using namespace std;
  26.  
  27. const double EPS = 1e-8;
  28. const double PI  = acos(-1.0);
  29. const double TAU = 2.0 * PI;
  30. const double INF = 1e99;
  31.  
  32. int sig(double x) {return x < -EPS ? -1 : x > EPS ? 1 : 0;}
  33. template<class T> T pow2(T x) {return x * x;}
  34.  
  35.  
  36. class Vector {
  37. public:
  38.     double x, y;
  39.     Vector() {}
  40.     Vector(double x, double y): x(x), y(y) {}
  41.  
  42.     Vector operator -() const {return Vector(-x, -y);}
  43.     Vector operator +(const Vector &v) const {return Vector(x+v.x, y+v.y);}
  44.     Vector operator -(const Vector &v) const {return Vector(x-v.x, y-v.y);}
  45.     Vector operator *(const double &s) const {return Vector(x * s, y * s);}
  46.     Vector operator /(const double &s) const {return Vector(x / s, y / s);}
  47.  
  48.     double operator *(const Vector &v) const {return x*v.x + y*v.y;}
  49.     double operator ^(const Vector &v) const {return x*v.y - y*v.x;}
  50.  
  51.     // rotate vector (Right/Left hand)
  52.     Vector  R(double co, double si) {return Vector(x*co-y*si, y*co+x*si);}
  53.     Vector  L(double co, double si) {return Vector(x*co+y*si, y*co-x*si);}
  54.     Vector  R(double th) {return R(cos(th), sin(th));}
  55.     Vector  L(double th) {return L(cos(th), sin(th));}
  56.  
  57.     double len2() {return x*x + y*y;}
  58.     double len()  {return sqrt(len2());}
  59.     double ang()  {return atan2(y, x);}  // angle of vector
  60.     Vector e(double s = 1.0) {return *this / len() * s;}
  61. };
  62. typedef Vector Point;
  63.  
  64.  
  65. class Line {
  66. public:
  67.     Point a, b;
  68.     Line() {}
  69.     Line(Point a, Point b): a(a), b(b) {}
  70. };
  71.  
  72. class Circle {
  73. public:
  74.     Point o;
  75.     double r;
  76.     Circle() {}
  77.     Circle(Point o, double r): o(o), r(r) {}
  78.  
  79.     // (d < R - r)         ----> -2
  80.     // (d = R - r)         ----> -1
  81.     // (d = 0)
  82.     // (R - r < d < R + r) ---->  0
  83.     // (d = R + r)         ---->  1
  84.     // (d > R + r)         ---->  2
  85.     int posi(Circle c) {
  86.         double d = (o - c.o).len();
  87.         int in = sig(d - fabs(r - c.r)), ex = sig(d - (r + c.r));
  88.         return in<0 ? -2 : in==0? -1 : ex==0 ? 1 : ex>0? 2 : 0;
  89.     }
  90.  
  91.  
  92.     Line chord(Circle c) {
  93.         Vector v = c.o - o;
  94.         double co = (pow2(r) + v.len2() - pow2(c.r)) / (2 * r * v.len());
  95.         double si = sqrt(fabs(1.0 - pow2(co)));
  96.         return Line(v.L(co, si).e(r) + o, v.R(co, si).e(r) + o);
  97.     }
  98. };
  99.  
  100.  
  101. // -PI <= th <= PI
  102. struct Range {
  103.     double t;
  104.     int evt;
  105.     Point p;
  106.     Range() {}
  107.     Range(double t, int evt, Point p) : t(t), evt(evt), p(p) {}
  108.  
  109.     bool operator <(const Range &s) const {
  110.         return sig(t - s.t) < 0 || (sig(t - s.t) == 0 && evt > s.evt);
  111.     }
  112. };
  113.  
  114.  
  115. const int MAX_N = 1000 + 10;
  116. Circle C[MAX_N];
  117. Range R[MAX_N<<1];
  118.  
  119. bool cmp_r(const Circle &a, const Circle &b) {
  120.     return a.r > b.r;
  121. }
  122.  
  123. double segment_area(double r, double t) {
  124.     return pow2(r) * (t - sin(t)) / 2;
  125. }
  126.  
  127. double union_circle(Circle C[], int &n)
  128. {
  129.     sort(C, C + n, cmp_r);
  130.     int k = 0;
  131.     for (int i = 0; i < n; i++) {
  132.         if (sig(C[i].r) == 0) break;
  133.         int j = 0;
  134.         for (j = 0; j < k; j++)
  135.             if (C[i].posi(C[j]) < 0 || !sig((C[i].o - C[j].o).len()))
  136.                 break;
  137.         if (j == k)
  138.             C[k++] = C[i];
  139.     }
  140.     n = k;
  141.  
  142.     double ans = 0;
  143.     for (int i = 0; i < n; ++ i)
  144.     {
  145.         Point mpi = Point(- C[i].r, 0.0) + C[i].o;
  146.         int nc = 0, rcnt = 0;
  147.         R[rcnt++] = Range(-PI,  1, mpi);
  148.         R[rcnt++] = Range( PI, -1, mpi);
  149.         for (int j = 0; j < n; ++ j)
  150.         {
  151.             if (j == i || C[i].posi(C[j])) continue;
  152.  
  153.             Line l = C[i].chord(C[j]);
  154.             double jR = (l.a - C[i].o).ang(), jL = (l.b - C[i].o).ang();
  155.  
  156.             if (sig(jR - jL) > 0) ++ nc;
  157.             R[rcnt++] = Range(jR,  1, l.a);
  158.             R[rcnt++] = Range(jL, -1, l.b);
  159.         }
  160.         sort(R, R + rcnt);
  161.  
  162.         double pj = - PI;
  163.         Point  pp = mpi;
  164.         for(int j = 0; j < rcnt; ++ j)
  165.         {
  166.             nc += R[j].evt;
  167.             if((nc == 2 && R[j].evt > 0) || nc == 0)
  168.                 ans += segment_area(C[i].r, R[j].t - pj) + (pp ^ R[j].p) / 2;
  169.             pj = R[j].t; pp = R[j].p;
  170.         }
  171.     }
  172.     return ans;
  173. }
  174.  
  175. int main(int argc, char *argv[])
  176. {
  177.     int n;
  178.     while (scanf("%d", &n) != EOF) {
  179.         for (int i = 0; i < n; i++)
  180.             scanf("%lf%lf%lf", &C[i].o.x, &C[i].o.y, &C[i].r);
  181.  
  182.         double ans = union_circle(C, n);
  183.         printf("%.5lf\n", ans);
  184.     }
  185.     return 0;
  186. }
Success #stdin #stdout 0s 15328KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w1j1o3
SCIRCLE VNSPOJ (VCIRCLES)
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!