http://acm.hdu.edu.cn/showproblem.php?pid=2892
解題思路：
求多邊形與圓的相交的面積是多少。
以圓心為頂點，將多邊形劃分為n個三角形。
接下來就求出每個三角形與圓相交的面積。
因為三角形的一個點是圓心，所以三角形的另外兩個點與圓的情況有以下幾種：
（1）兩點都在圓裡，三角形與圓相交的面積=三角形的面積。
（2）一個點在圓外，一個點在圓裡，三角形與圓相交的面積=小三角形的面積+扇形面積
（3）兩點都在圓外，又分為幾種情況：
1、兩點構成的線段與圓相交的點數0或1個時，三角形與圓相交的面積=扇形的面積
2.兩點構成的線段與圓相交的點數2個時，三角形與圓相交的面積=大扇形面積+小三角形面積-小扇形的面積
1 #include<cmath>
2 #include<cstdio>
3 #include<vector>
4 #include<algorithm>
5 using namespace std;
6
7 #define MAXN 100000+10
8 #define PI acos(-1.0)
9 #define EPS 0.00000001
10
11 int dcmp(double x){
12 if(fabs(x) < EPS)
13 return 0;
14 return x < 0 ? -1 : 1;
15 }
16
17 struct Point{
18 double x, y;
19 Point(double x = 0, double y = 0): x(x), y(y) {}
20 };
21
22 struct Circle{
23 Point c;
24 double r;
25 Circle(Point c = Point(0, 0), double r = 0): c(c), r(r) {}
26 };
27
28 typedef Point Vector;
29
30 Vector operator + (Vector A, Vector B){
31 return Vector(A.x + B.x, A.y + B.y);
32 }
33 Vector operator - (Point A, Point B){
34 return Vector(A.x - B.x, A.y - B.y);
35 }
36 Vector operator * (Vector A, double p){
37 return Vector(A.x * p, A.y * p);
38 }
39 Vector operator / (Vector A, double p){
40 return Vector(A.x / p, A.y / p);
41 }
42
43 double dot(Vector A, Vector B){
44 return A.x * B.x + A.y * B.y;
45 }
46
47 double length(Vector A){
48 return sqrt(dot(A, A));
49 }
50
51 double angle(Vector A, Vector B){
52 return acos(dot(A, B) / length(A) / length(B));
53 }
54
55 double cross(Vector A, Vector B){
56 return A.x * B.y - A.y * B.x;
57 }
58
59 Circle bomb;//炸彈爆炸的坐標及半徑
60 Point p[MAXN];//島嶼的點
61 int n;//島嶼點數
62
63 double point_line_distance(Point P, Point A, Point B){//點到直線的距離
64 Vector AP = P - A, AB = B - A;
65 return fabs(cross(AP, AB) / length(AB));
66 }
67
68 Point point_line_projection(Point P, Point A, Point B){//點在直線上的映射
69 Vector v = B - A;
70 return A + v * (dot(v, P - A) / dot(v, v));
71 }
72
73 int circle_line_intersect(Circle C, Point A, Point B, vector<Point> &v){
74 double dist = point_line_distance(C.c, A, B);
75 int d = dcmp(dist - C.r);
76 if(d > 0){
77 return 0;
78 }
79 Point pro = point_line_projection(C.c, A, B);
80 if(d == 0){
81 v.push_back(pro);
82 return 1;
83 }
84 double len = sqrt(C.r * C.r - dist * dist);//勾股定理
85 Vector AB = B - A;
86 Vector l = AB / length(AB) * len;
87 v.push_back(pro + l);
88 v.push_back(pro - l);
89 return 2;
90 }
91
92 bool point_on_segment(Point P, Point A, Point B){//判斷點在線段上
93 Vector PA = A - P, PB = B - P;
94 return dcmp(cross(PA, PB)) == 0 && dcmp(dot(PA, PB)) <= 0;
95 }
96
97 double circle_delta_intersect_area(Circle C, Point A, Point B){
98 Vector CA = A - C.c, CB = B - C.c;
99 double da = length(CA), db = length(CB);
100
101 da = dcmp(da - C.r), db = dcmp(db - C.r);
102
103 if(da <= 0 && db <= 0){//三角形在圓裡面
104 return fabs(cross(CA, CB)) * 0.5;
105 }
106
107 vector<Point> v;
108 int num = circle_line_intersect(C, A, B, v);//圓和直線的關系
109 double carea = C.r * C.r * PI;
110 Point t;
111 if(da <= 0 && db > 0){//左邊的點在圓裡 右邊的點在圓外
112 t = point_on_segment(v[0], A, B) ? v[0] : v[1];
113
114 double area = fabs(cross(CA, t - C.c)) * 0.5, an = angle(CB, t - C.c);
115 return area + carea * an / PI / 2;
116 }
117 if(da > 0 && db <= 0){//左邊點在圓外 右邊點在圓裡
118 t = point_on_segment(v[0], A, B) ? v[0] : v[1];
119
120 double area = fabs(cross(CB, t - C.c)) * 0.5, an = angle(CA, t - C.c);
121 return area + carea * an / PI / 2;
122 }
123 //兩個點都在圓外
124 if(num == 2){
125 double bigarea = carea * angle(CA, CB) / PI / 2,
126 smallarea = carea * angle(v[0] - C.c, v[1] - C.c) / PI / 2,
127 deltaarea = fabs(cross(v[0] - C.c, v[1] - C.c)) * 0.5;
128 return bigarea + deltaarea - smallarea;
129 }
130 return carea * angle(CA, CB) / PI / 2;//兩點都在圓外 直線AB與圓交點1個或兩個
131 }
132
133 double circle_polygon_intersect_area(){//源於多邊形相交面積
134 p[n] = p[0];
135 double ans = 0;
136 for(int i = 0; i < n; i++ ){
137 double area = circle_delta_intersect_area( bomb, p[i], p[i + 1] );
138 if(cross(p[i] - bomb.c, p[i + 1] - bomb.c) < 0){
139 area = -area;
140 }
141 ans += area;
142 }
143 return ans > 0 ? ans : -ans;
144 }
145
146 void solve(){
147 scanf("%d", &n );
148 for(int i = 0; i < n; i++ ){
149 scanf("%lf%lf", &p[i].x, &p[i].y );
150 }
151 printf("%.2lf\n", circle_polygon_intersect_area() );
152 }
153
154 int main(){
155 //freopen("data.in", "r", stdin );
156 double x, y, h, x1, y1, r;
157 while(~scanf("%lf%lf%lf", &x, &y, &h )){
158 scanf("%lf%lf%lf", &x1, &y1, &r );
159
160 double t = sqrt(0.2 * h);//h = 0.5 * G * t^2 重力加速度公式
161
162 bomb = Circle( Point(x1 * t + x, y1 * t + y), r );
163
164 solve();
165 }
166 return 0;
167 }
赤裸的BFS，但是要注意下標記，得用x，y，t三維標記。因為有些坐標有經過多次來重置炸彈。。
貼下我的代碼。。
#include<stdio.h>
struct queue
{
int x;
int y;
int time;
int t;
}a[200000];
int si,sj,ei,ej,n,m,d[4][2]={-1,0,1,0,0,-1,0,1};
int map[10][10],hash[10][10][10];
int bfs()
{
int i,x1,y1,t1,head,tail;
a[0].x=si;
a[0].y=sj;
a[0].time=0;
a[0].t=6;
head=0;tail=1;
while(head<tail)
{
// printf("\n%d %d %d %d\n",a[head].x,a[head].y,a[head].time,a[head].t);
// printf("-----------------------------------\n");
for(i=0;i<4;i++)
{
if(a[head].t<2)
break;
x1=a[head].x+d[i][0];
y1=a[head].y+d[i][1];
if(map[x1][y1]==4)
t1=6;
else
t1=a[head].t-1;
if(hash[x1][y1][t1])
continue;
if(x1<0||x1>=n||y1<0||y1>=m)
continue;
if(map[x1][y1]==0)
continue;
a[tail].x=x1;
a[tail].y=y1;
a[tail].t=t1;
a[tail].time=a[head].time+1;
hash[x1][y1][a[tail].t]=1; //注意這裡的標記。
// printf("%d %d %d %d\n",a[tail].x,a[tail].y,a[tail].time,a[tail].t);
if(x1==ei&&y1==ej)
return (a[head].time+1);
tail++;
}
// printf("\n");
head++;
}
return 0;
}......余下全文>>
