POJ 2986 A Triangle and a Circle 圆与三角形的公共面积

计算几何模板
  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<stdlib.h>
  4 #include<math.h>
  5 #include<algorithm>
  6 
  7 const double eps = 1e-8;
  8 const double pi = acos(-1.0);
  9 
 10 int dcmp(double x)
 11 {
 12     if(x > eps) return 1;
 13     return x < -eps ? -1 : 0;
 14 }
 15 
 16 struct Point
 17 {
 18     double x, y;
 19     Point()
 20     {
 21         x = y = 0;
 22     }
 23     Point(double a, double b)
 24     {
 25         x = a, y = b;
 26     }
 27     inline void read()
 28     {
 29         scanf("%lf%lf", &x, &y);
 30     }
 31     inline Point operator-(const Point &b)const
 32     {
 33         return Point(x - b.x, y - b.y);
 34     }
 35     inline Point operator+(const Point &b)const
 36     {
 37         return Point(x + b.x, y + b.y);
 38     }
 39     inline Point operator*(const double &b)const
 40     {
 41         return Point(x * b, y * b);
 42     }
 43     inline double dot(const Point &b)const
 44     {
 45         return x * b.x + y * b.y;
 46     }
 47     inline double cross(const Point &b, const Point &c)const
 48     {
 49         return (b.x - x) * (c.y - y) - (c.x - x) * (b.y - y);
 50     }
 51     inline double Dis(const Point &b)const
 52     {
 53         return sqrt((*this - b).dot(*this - b));
 54     }
 55     inline bool InLine(const Point &b, const Point &c)const//三点共线
 56     {
 57         return !dcmp(cross(b, c));
 58     }
 59     inline bool OnSeg(const Point &b, const Point &c)const//点在线段上，包括端点
 60     {
 61         return InLine(b, c) && (*this - c).dot(*this - b) < eps;
 62     }
 63 };
 64 
 65 inline double min(double a, double b)
 66 {
 67     return a < b ? a : b;
 68 }
 69 inline double max(double a, double b)
 70 {
 71     return a > b ? a : b;
 72 }
 73 inline double Sqr(double x)
 74 {
 75     return x * x;
 76 }
 77 inline double Sqr(const Point &p)
 78 {
 79     return p.dot(p);
 80 }
 81 
 82 Point LineCross(const Point &a, const Point &b, const Point &c, const Point &d)
 83 {
 84     double u = a.cross(b, c), v = b.cross(a, d);
 85     return Point((c.x * v + d.x * u) / (u + v), (c.y * v + d.y * u) / (u + v));
 86 }
 87 
 88 double LineCrossCircle(const Point &a, const Point &b, const Point &r,
 89                        double R, Point &p1, Point &p2)
 90 {
 91     Point fp = LineCross(r, Point(r.x + a.y - b.y, r.y + b.x - a.x), a, b);
 92     double rtol = r.Dis(fp);
 93     double rtos = fp.OnSeg(a, b) ? rtol : min(r.Dis(a), r.Dis(b));
 94     double atob = a.Dis(b);
 95     double fptoe = sqrt(R * R - rtol * rtol) / atob;
 96     if(rtos > R - eps) return rtos;
 97     p1 = fp + (a - b) * fptoe;
 98     p2 = fp + (b - a) * fptoe;
 99     return rtos;
100 }
101 
102 double SectorArea(const Point &r, const Point &a, const Point &b, double R)
103 //不大于180度扇形面积，r->a->b逆时针
104 {
105     double A2 = Sqr(r - a), B2 = Sqr(r - b), C2 = Sqr(a - b);
106     return R * R * acos((A2 + B2 - C2) * 0.5 / sqrt(A2) / sqrt(B2)) * 0.5;
107 }
108 
109 double TACIA(const Point &r, const Point &a, const Point &b, double R)
110 //TriangleAndCircleIntersectArea，逆时针，r为圆心
111 {
112     double adis = r.Dis(a), bdis = r.Dis(b);
113     if(adis < R + eps && bdis < R + eps) return r.cross(a, b) * 0.5;
114     Point ta, tb;
115     if(r.InLine(a, b)) return 0.0;
116     double rtos = LineCrossCircle(a, b, r, R, ta, tb);
117     if(rtos > R - eps) return SectorArea(r, a, b, R);
118     if(adis < R + eps) return r.cross(a, tb) * 0.5 + SectorArea(r, tb, b, R);
119     if(bdis < R + eps) return r.cross(ta, b) * 0.5 + SectorArea(r, a, ta, R);
120     return r.cross(ta, tb) * 0.5 +
121            SectorArea(r, a, ta, R) + SectorArea(r, tb, b, R);
122 }
123 
124 const int N = 505;
125 
126 Point p[N];
127 
128 double SPICA(int n, Point r, double R)//SimplePolygonIntersectCircleArea
129 {
130     int i;
131     double res = 0, if_clock_t;
132     for(i = 0; i < n; ++ i)
133     {
134         if_clock_t = dcmp(r.cross(p[i], p[(i + 1) % n]));
135         if(if_clock_t < 0) res -= TACIA(r, p[(i + 1) % n], p[i], R);
136         else res += TACIA(r, p[i], p[(i + 1) % n], R);
137     }
138     return fabs(res);
139 }
140 
141 double r;
142 
143 int main()
144 {
145     while (~scanf("%lf%lf", &p[0].x, &p[0].y))
146     {
147         for (int i = 1; i < 4; i++)
148             p[i].read();
149         scanf("%lf", &r);
150         printf("%.2f
", SPICA(3, p[3], r));
151     }
152     return 0;
153 }
View Code