题意：给你一个圆形和很多个矩形，然后要你求圆形的圆周有多少被矩形覆盖。
思路：比赛的时候是有思路的了，不过一直在调别的题，最后剩下30分钟肯定来不及敲。想法是这样的，要是我们可以求出每个矩形覆盖了圆周的哪些区间，我们最后就对这些区间排序然后求区间和就好了，但是问题是怎么知道哪些区间是要的，哪些区间是不要的呢？ 首先我们对矩形的四条线段和矩形求交，把所有的交点求出来，然后将交点用atan2转化成极角（我用的区间是[0,2pi]），实际上直接用极角肯定也没问题吧），然后排序，排序之后我们会发现我们要的区间一定是相邻的两个角度的点对应的区间，但是有可能这些区间是不是我们要的，判断的条件就是两个角度的对应的弧段的中点如果在矩形里面的话我们就将这个区间保留。
如此一来就将所有的区间弄了出来，接下来就是求线段的并的总长度了，for一下就好。
但是后来WA了一发，原因是如果圆完全被矩形包含的话，我们解不出交点，会被默认答案是0，所以上面的方法只有在有交点的时候成立，所以判的时候加多一个判是否被完全包含，被完全包含最后直接输出2*pi*r就好，代码写的略长＝ ＝
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181 |
#pragma warning(disable:4996)#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#include<cmath>#include<string>#define maxn 150#define eps 1e-7using
namespace std;const
double pi = acos(-1.0);struct
Point{ double
x, y; Point(double
xi, double
yi) :x(xi), y(yi){} Point(){} Point operator + (const
Point &b){ return
Point(x + b.x, y + b.y); } Point operator - (const
Point &b){ return
Point(x - b.x, y - b.y); } double
ang(){ double
res=atan2(y,x); if
(res < 0) return
res + 2*pi; else
return res; } Point rot(double
ag){ return
Point(x*cos(ag) - y*sin(ag), x*sin(ag) + y*cos(ag)); }};struct
Seg{ Point st, ed; Seg(Point sti, Point edi) :st(sti), ed(edi){} Seg(){}};struct
Inter{ double
l, r; Inter(double
li, double
ri) :l(li), r(ri){} Inter(){} bool
operator < (const
Inter &b) const{ if
(l == b.l) return
r < b.r; else
return l < b.l; }};int
dcmp(double
x){ return
(x>eps) - (x < -eps);}double
ctr;int
n;vector<double> getInterSection(Seg seg){ vector<double> res; if
(seg.st.x == seg.ed.x){ double
xx = seg.st.x; double
y1 = seg.st.y, y2 = seg.ed.y; if
(dcmp(abs(xx) - ctr) > 0) return
res; else
if (dcmp(abs(xx) - ctr) == 0){ if
(0 >= y1 && 0 <= y2){ res.push_back(Point(xx, 0).ang()); } } else{ double
dy = sqrt(ctr*ctr - xx*xx); if
(dy >= y1&&dy <= y2){ res.push_back(Point(xx, dy).ang()); } dy = -dy; if
(dy >= y1&&dy <= y2){ res.push_back(Point(xx, dy).ang()); } } } else{ double
yy = seg.st.y; double
x1 = seg.st.x, x2 = seg.ed.x; if
(dcmp(abs(yy) - ctr) > 0) return
res; else
if (dcmp(abs(yy) - ctr) == 0){ if
(0 >= x1 && 0 <= x2){ res.push_back(Point(0, yy).ang()); } } else{ double
dx = sqrt(ctr*ctr - yy*yy); if
(dx >= x1&&dx <= x2){ res.push_back(Point(dx, yy).ang()); } dx = -dx; if
(dx >= x1&&dx <= x2){ res.push_back(Point(dx, yy).ang()); } } } return
res;}bool
withinRect(double
xx,double
yy, double
li, double
lj, double
ri, double
rj){ return
xx >= li&&xx <= ri&&yy >= lj&&yy <= rj;}int
main(){ while
(cin >> ctr >> n){ double
li, lj, ri, rj; Seg seg; vector<double> tot; vector<double> tmp; vector<Inter> inter; bool
flag = false; for
(int i = 0; i < n; i++){ scanf("%lf%lf%lf%lf", &li, &lj, &ri, &rj); if
(flag) continue; if
(li <= -ctr && ctr <= ri && lj <= -ctr&&ctr <= rj){ flag = true; continue; } tot.clear(); seg.st = Point(li, lj); seg.ed = Point(li, rj); tmp = getInterSection(seg); tot.insert(tot.end(), tmp.begin(), tmp.end()); seg.st = Point(ri, lj); seg.ed = Point(ri, rj); tmp = getInterSection(seg); tot.insert(tot.end(), tmp.begin(), tmp.end()); seg.st = Point(li, lj); seg.ed = Point(ri, lj); tmp = getInterSection(seg); tot.insert(tot.end(), tmp.begin(), tmp.end()); seg.st = Point(li, rj); seg.ed = Point(ri, rj); tmp = getInterSection(seg); tot.insert(tot.end(), tmp.begin(), tmp.end()); sort(tot.begin(), tot.end()); int
siz = tot.size(); for
(int k = 0; k < siz; k++){ if
(dcmp(tot[k] - tot[(k + 1) % siz]) == 0) continue; Point mid; if
(dcmp(tot[(k + 1) % siz] - tot[k])>0) mid = Point(ctr, 0).rot((tot[k] + tot[(k + 1) % siz]) / 2); else
mid = Point(ctr, 0).rot((tot[k] + tot[(k + 1) % siz]-2*pi) / 2); if
(withinRect(mid.x, mid.y, li, lj, ri, rj)){ if
(dcmp(tot[(k + 1) % siz] - tot[k]) >= 0){ inter.push_back(Inter(tot[k], tot[(k + 1) % siz])); } else{ inter.push_back(Inter(0, tot[(k+1)%siz])); inter.push_back(Inter(tot[k % siz], 2 * pi)); } } } } sort(inter.begin(), inter.end()); double
ans = 0; if
(flag) { printf("%.3lf\n", 2 * pi*ctr); continue; } if
(inter.size() == 0) { printf("%.3lf\n", ans); continue; } double
lt = inter[0].l, rt = inter[0].r; for
(int i = 1; i < inter.size(); i++){ if
(inter[i].l <= rt){ rt = max(rt, inter[i].r); } else{ ans += rt - lt; lt = inter[i].l, rt = inter[i].r; } } ans += rt - lt; printf("%.3lf\n", ans*ctr); } return
0;} |
ZOJ3238 Water Ring(计算几何),布布扣,bubuko.com
原文：http://www.cnblogs.com/chanme/p/3643782.html