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}