POJ 2546 - Circular Area

http://poj.org/problem?id=2546

概要

2つの円の中心座標と半径がそれぞれ与えられるので，共通部分の面積を答える．

制約

解法

がんばって計算する．

 1 #include <cstdio>
 2 #include <complex>
 3 #include <cmath>
 4 using namespace std;
 5 typedef complex<double> P;
 6 static const double PI = atan2(+0.0, -0.0);
 7 static const double EPS = 1e-6;
 8 
 9 inline double cross(const P& a, const P& b)
10 {
11   return a.real()*b.imag() - b.real()*a.imag();
12 }
13 
14 struct segment
15 {
16   P a, b;
17   segment() {}
18   segment(const P& x, const P& y) : a(x), b(y) {}
19   inline double distance(const P& p) const
20   {
21     return abs(cross(p - a, b - a)) / abs(b - a);
22   }
23   inline double length() const { return abs(b - a); }
24   inline P intersect(const segment& seg) const
25   {
26     const double d1 = seg.distance(a);
27     const double d2 = seg.distance(b);
28     const double t = d1 / (d1 + d2);
29     return (1-t)*a + t*b;
30   }
31 };
32 
33 struct circle
34 {
35   P o;
36   double r;
37   circle() {}
38   circle(const P& o_, double r_) : o(o_), r(r_) {}
39 
40   inline double area() const { return PI*r*r; }
41   double intersection_area(const circle& c) const
42   {
43     const double d = abs(c.o - o);
44     //if (d > r + c.r) {
45     if (r + c.r - d < EPS) {
46       return 0.0;
47     //} else if (d < abs(r - c.r)) {
48     } else if (d - abs(r - c.r) < EPS) {
49       const double r1 = min(r, c.r);
50       return r1*r1*PI;
51     } else {
52       const double cos_ = (d*d + r*r - c.r*c.r) / (2*d);
53       const double theta = acos(cos_ / r);
54       const double phi = acos((d - cos_) / c.r);
55       return r*r*theta + c.r*c.r*phi - d*r*sin(theta);
56     }
57   }
58 };
59 
60 int main()
61 {
62   double x1, y1, r1, x2, y2, r2;
63   scanf("%lf %lf %lf %lf %lf %lf\n", &x1, &y1, &r1, &x2, &y2, &r2);
64   const circle c1(P(x1, y1), r1), c2(P(x2, y2), r2);
65   printf("%.3f\n", c1.intersection_area(c2));
66   return 0;
67 }
poj/2546.cc