spoj CIRU - The area of the union of circles (多个圆面积并,模板题)
题意:
多n个圆的面积并。
思路:
发现和求2个圆的完全不一样,具体请参考
SPOJ 8073 The area of the union of circles(计算几何の圆并)(CIRU)
(用格林公式搞真是跪烂了。。。。
没有仔细看细节,当成板子好了(我最菜.jpg
将代码写成了自己熟悉的风格。
以及双倍经验题:SPOJ VCIRCLES
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月11日 星期三 19时53分30秒
4File Name :ciru.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const double PI = acos(-1.0);
35const int N =1e3+7;
36inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
37struct point
38{
39 double x,y;
40 point(){}
41 point(double x,double y):x(x),y(y){}
42 void input(){scanf("%lf%lf",&x,&y);}
43 double angle(){ return atan2(y,x);}
44 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
45 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
46 point operator * (double t)const{ return point(t*x,t*y);}
47 point operator / (double t)const{ return point(x/t,y/t);}
48 double length() const { return sqrt(x*x+y*y);};
49 point unit()const { double l = length();return point(x/l,y/l); }
50};
51double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
52double dist(const point p1,point p2) { return (p1-p2).length();}
53point rotate(point p,double angle,point o = point(0,0))
54{ point t = p-o;
55 double x = t.x * cos(angle) - t.y*sin(angle);
56 double y = t.y * cos(angle) + t.x*sin(angle);
57 return point (x,y)+o;
58}
59struct region{
60 double st,ed;
61 region(){}
62 region(double st,double ed):st(st),ed(ed){}
63 bool operator < (const region & rhs)const
64 { if (dblcmp(st-rhs.st)) return st<rhs.st;
65 return ed<rhs.ed;
66 }
67};
68struct circle{
69 point c;
70 double r;
71 vector <region>reg;
72 circle(){}
73 circle(point c,double r):c(c),r(r){}
74 void input()
75 {
76 c.input();
77 scanf("%lf",&r);
78 }
79 void add(const region &r){ reg.PB(r);}
80 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
81 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
82};
83double sqr( double x){ return x*x;}
84void intersection(circle cir1,circle cir2,point &p1,point &p2)
85{
86 double l = dist(cir1.c,cir2.c);
87 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
88 double d2 = sqrt(sqr(cir1.r)-sqr(d));
89 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
90 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
91 p1 = mid + v,p2 = mid -v;
92}
93point calc(const circle &cir,double angle)
94{
95 point p = point (cir.c.x+cir.r,cir.c.y);
96 return rotate(p,angle,cir.c);
97}
98
99circle cir[N];
100bool del[N];
101int n;
102
103double solve()
104{
105 double ans = 0 ;
106 for ( int i = 0 ; i < n ; i++){
107 for ( int j = 0 ; j < n ; j++) if (!del[j]){
108 if (i==j) continue;
109 if (cir[j].contain(cir[i]))
110 { del[i] = true;
111 break;
112 }
113 }
114 }
115 for ( int i = 0 ; i < n ; i++) if (!del[i]){
116 circle &mc = cir[i];
117 point p1,p2;
118 bool flag = false;
119 for ( int j = 0 ; j < n ; j++) if (!del[j]){
120 if (i==j) continue;
121 if (!mc.interect(cir[j])) continue;
122 flag = true;
123 intersection(mc,cir[j],p1,p2);
124 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
125 if (dblcmp(rs)<0) rs+=2*PI;
126 if (dblcmp(rt)<0) rt+=2*PI;
127 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
128 else mc.add(region(rs,rt));
129 }
130 if (!flag) { ans += PI*sqr(mc.r); continue;}
131 sort(mc.reg.begin(),mc.reg.end());
132 int cnt = 1;
133 for ( int j = 1 ; j < mc.reg.size() ; j++)
134 {
135 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
136 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
137 else mc.reg[cnt++] = mc.reg[j];
138 }
139 mc.add(region());
140 mc.reg[cnt]=mc.reg[0];
141 for ( int j = 0 ; j < cnt ; j++)
142 {
143 p1 = calc(mc,mc.reg[j].ed);
144 p2 = calc(mc,mc.reg[j+1].st);
145 ans +=cross(p1,p2)/2;
146 double angle = mc.reg[j+1].st - mc.reg[j].ed;
147 if (dblcmp(angle)<0) angle+=2*PI;
148 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
149 }
150 }
151 return ans;
152
153}
154int main()
155{
156 #ifndef ONLINE_JUDGE
157 freopen("./in.txt","r",stdin);
158 #endif
159
160 scanf("%d",&n);
161 for ( int i = 0 ; i < n ; i++) cir[i].input();
162 printf("%.3f\n",solve());
163 #ifndef ONLINE_JUDGE
164 fclose(stdin);
165 #endif
166 return 0;
167}
168
169
170
171
172
173
174
175
176
177
178/* ***********************************************
179Author :111qqz
180Created Time :2017年10月11日 星期三 19时53分30秒
181File Name :ciru.cpp
182************************************************ */
183
184#include <cstdio>
185#include <cstring>
186#include <iostream>
187#include <algorithm>
188#include <vector>
189#include <queue>
190#include <set>
191#include <map>
192#include <string>
193#include <cmath>
194#include <cstdlib>
195#include <ctime>
196#define PB push_back
197#define fst first
198#define sec second
199#define lson l,m,rt<<1
200#define rson m+1,r,rt<<1|1
201#define ms(a,x) memset(a,x,sizeof(a))
202typedef long long LL;
203#define pi pair < int ,int >
204#define MP make_pair
205
206using namespace std;
207const double eps = 1E-8;
208const int dx4[4]={1,0,0,-1};
209const int dy4[4]={0,-1,1,0};
210const int inf = 0x3f3f3f3f;
211const double PI = acos(-1.0);
212const int N =1e3+7;
213inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
214struct point
215{
216 double x,y;
217 point(){}
218 point(double x,double y):x(x),y(y){}
219 void input(){scanf("%lf%lf",&x,&y);}
220 double angle(){ return atan2(y,x);}
221 point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
222 point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
223 point operator * (double t)const{ return point(t*x,t*y);}
224 point operator / (double t)const{ return point(x/t,y/t);}
225 double length() const { return sqrt(x*x+y*y);};
226 point unit()const { double l = length();return point(x/l,y/l); }
227};
228double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
229double dist(const point p1,point p2) { return (p1-p2).length();}
230point rotate(point p,double angle,point o = point(0,0))
231{ point t = p-o;
232 double x = t.x * cos(angle) - t.y*sin(angle);
233 double y = t.y * cos(angle) + t.x*sin(angle);
234 return point (x,y)+o;
235}
236struct region{
237 double st,ed;
238 region(){}
239 region(double st,double ed):st(st),ed(ed){}
240 bool operator < (const region & rhs)const
241 { if (dblcmp(st-rhs.st)) return st<rhs.st;
242 return ed<rhs.ed;
243 }
244};
245struct circle{
246 point c;
247 double r;
248 vector <region>reg;
249 circle(){}
250 circle(point c,double r):c(c),r(r){}
251 void input()
252 {
253 c.input();
254 scanf("%lf",&r);
255 }
256 void add(const region &r){ reg.PB(r);}
257 bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
258 bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
259};
260double sqr( double x){ return x*x;}
261void intersection(circle cir1,circle cir2,point &p1,point &p2)
262{
263 double l = dist(cir1.c,cir2.c);
264 double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
265 double d2 = sqrt(sqr(cir1.r)-sqr(d));
266 point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
267 point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
268 p1 = mid + v,p2 = mid -v;
269}
270point calc(const circle &cir,double angle)
271{
272 point p = point (cir.c.x+cir.r,cir.c.y);
273 return rotate(p,angle,cir.c);
274}
275
276circle cir[N];
277bool del[N];
278int n;
279
280double solve()
281{
282 double ans = 0 ;
283 for ( int i = 0 ; i < n ; i++){
284 for ( int j = 0 ; j < n ; j++) if (!del[j]){
285 if (i==j) continue;
286 if (cir[j].contain(cir[i]))
287 { del[i] = true;
288 break;
289 }
290 }
291 }
292 for ( int i = 0 ; i < n ; i++) if (!del[i]){
293 circle &mc = cir[i];
294 point p1,p2;
295 bool flag = false;
296 for ( int j = 0 ; j < n ; j++) if (!del[j]){
297 if (i==j) continue;
298 if (!mc.interect(cir[j])) continue;
299 flag = true;
300 intersection(mc,cir[j],p1,p2);
301 double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
302 if (dblcmp(rs)<0) rs+=2*PI;
303 if (dblcmp(rt)<0) rt+=2*PI;
304 if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
305 else mc.add(region(rs,rt));
306 }
307 if (!flag) { ans += PI*sqr(mc.r); continue;}
308 sort(mc.reg.begin(),mc.reg.end());
309 int cnt = 1;
310 for ( int j = 1 ; j < mc.reg.size() ; j++)
311 {
312 if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
313 mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
314 else mc.reg[cnt++] = mc.reg[j];
315 }
316 mc.add(region());
317 mc.reg[cnt]=mc.reg[0];
318 for ( int j = 0 ; j < cnt ; j++)
319 {
320 p1 = calc(mc,mc.reg[j].ed);
321 p2 = calc(mc,mc.reg[j+1].st);
322 ans +=cross(p1,p2)/2;
323 double angle = mc.reg[j+1].st - mc.reg[j].ed;
324 if (dblcmp(angle)<0) angle+=2*PI;
325 ans+=0.5*sqr(mc.r)*(angle-sin(angle));
326 }
327 }
328 return ans;
329
330}
331int main()
332{
333 #ifndef ONLINE_JUDGE
334 freopen("./in.txt","r",stdin);
335 #endif
336
337 scanf("%d",&n);
338 for ( int i = 0 ; i < n ; i++) cir[i].input();
339 printf("%.5f\n",solve());
340 #ifndef ONLINE_JUDGE
341 fclose(stdin);
342 #endif
343 return 0;
344}