spoj CIRU - The area of the union of circles (多个圆面积并，模板题)
题意：
多n个圆的面积并。
思路：
发现和求2个圆的完全不一样，具体请参考
SPOJ 8073 The area of the union of circles（计算几何の圆并）（CIRU）
（用格林公式搞真是跪烂了。。。。
没有仔细看细节，当成板子好了(我最菜.jpg
将代码写成了自己熟悉的风格。
以及双倍经验题:SPOJ VCIRCLES
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N =1e3+7;
inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
struct point
{
double x,y;
point(){}
point(double x,double y):x(x),y(y){}
void input(){scanf("%lf%lf",&x,&y);}
double angle(){ return atan2(y,x);}
point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
point operator * (double t)const{ return point(t*x,t*y);}
point operator / (double t)const{ return point(x/t,y/t);}
double length() const { return sqrt(x*x+y*y);};
point unit()const { double l = length();return point(x/l,y/l); }
};
double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
double dist(const point p1,point p2) { return (p1-p2).length();}
point rotate(point p,double angle,point o = point(0,0))
{ point t = p-o;
double x = t.x * cos(angle) - t.y*sin(angle);
double y = t.y * cos(angle) + t.x*sin(angle);
return point (x,y)+o;
}
struct region{
double st,ed;
region(){}
region(double st,double ed):st(st),ed(ed){}
bool operator < (const region & rhs)const
{ if (dblcmp(st-rhs.st)) return st<rhs.st;
return ed<rhs.ed;
}
};
struct circle{
point c;
double r;
vector <region>reg;
circle(){}
circle(point c,double r):c(c),r(r){}
void input()
{
c.input();
scanf("%lf",&r);
}
void add(const region &r){ reg.PB(r);}
bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
};
double sqr( double x){ return x*x;}
void intersection(circle cir1,circle cir2,point &p1,point &p2)
{
double l = dist(cir1.c,cir2.c);
double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
double d2 = sqrt(sqr(cir1.r)-sqr(d));
point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
p1 = mid + v,p2 = mid -v;
}
point calc(const circle &cir,double angle)
{
point p = point (cir.c.x+cir.r,cir.c.y);
return rotate(p,angle,cir.c);
}
circle cir[N];
bool del[N];
int n;
double solve()
{
double ans = 0 ;
for ( int i = 0 ; i < n ; i++){
for ( int j = 0 ; j < n ; j++) if (!del[j]){
if (i==j) continue;
if (cir[j].contain(cir[i]))
{ del[i] = true;
break;
}
}
}
for ( int i = 0 ; i < n ; i++) if (!del[i]){
circle &mc = cir[i];
point p1,p2;
bool flag = false;
for ( int j = 0 ; j < n ; j++) if (!del[j]){
if (i==j) continue;
if (!mc.interect(cir[j])) continue;
flag = true;
intersection(mc,cir[j],p1,p2);
double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
if (dblcmp(rs)<0) rs+=2*PI;
if (dblcmp(rt)<0) rt+=2*PI;
if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
else mc.add(region(rs,rt));
}
if (!flag) { ans += PI*sqr(mc.r); continue;}
sort(mc.reg.begin(),mc.reg.end());
int cnt = 1;
for ( int j = 1 ; j < mc.reg.size() ; j++)
{
if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
else mc.reg[cnt++] = mc.reg[j];
}
mc.add(region());
mc.reg[cnt]=mc.reg[0];
for ( int j = 0 ; j < cnt ; j++)
{
p1 = calc(mc,mc.reg[j].ed);
p2 = calc(mc,mc.reg[j+1].st);
ans +=cross(p1,p2)/2;
double angle = mc.reg[j+1].st - mc.reg[j].ed;
if (dblcmp(angle)<0) angle+=2*PI;
ans+=0.5*sqr(mc.r)*(angle-sin(angle));
}
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
scanf("%d",&n);
for ( int i = 0 ; i < n ; i++) cir[i].input();
printf("%.3f\n",solve());
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
/* ***********************************************
Author :111qqz
Created Time :2017年10月11日 星期三 19时53分30秒
File Name :ciru.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
const int N =1e3+7;
inline int dblcmp( double d) { return d<-eps?-1:d>eps;}
struct point
{
double x,y;
point(){}
point(double x,double y):x(x),y(y){}
void input(){scanf("%lf%lf",&x,&y);}
double angle(){ return atan2(y,x);}
point operator + (const point &rhs)const{ return point(x+rhs.x,y+rhs.y);}
point operator - (const point &rhs)const{ return point(x-rhs.x,y-rhs.y);}
point operator * (double t)const{ return point(t*x,t*y);}
point operator / (double t)const{ return point(x/t,y/t);}
double length() const { return sqrt(x*x+y*y);};
point unit()const { double l = length();return point(x/l,y/l); }
};
double cross (const point a,point b){ return a.x*b.y-a.y*b.x ;}
double dist(const point p1,point p2) { return (p1-p2).length();}
point rotate(point p,double angle,point o = point(0,0))
{ point t = p-o;
double x = t.x * cos(angle) - t.y*sin(angle);
double y = t.y * cos(angle) + t.x*sin(angle);
return point (x,y)+o;
}
struct region{
double st,ed;
region(){}
region(double st,double ed):st(st),ed(ed){}
bool operator < (const region & rhs)const
{ if (dblcmp(st-rhs.st)) return st<rhs.st;
return ed<rhs.ed;
}
};
struct circle{
point c;
double r;
vector <region>reg;
circle(){}
circle(point c,double r):c(c),r(r){}
void input()
{
c.input();
scanf("%lf",&r);
}
void add(const region &r){ reg.PB(r);}
bool contain (const circle & cir)const{ return dblcmp(dist(cir.c,c)+cir.r-r)<=0;}
bool interect (const circle & cir)const{ return dblcmp(dist(cir.c,c)-cir.r-r)<0;}
};
double sqr( double x){ return x*x;}
void intersection(circle cir1,circle cir2,point &p1,point &p2)
{
double l = dist(cir1.c,cir2.c);
double d = (sqr(l)-sqr(cir2.r) + sqr(cir1.r))/(2*l);
double d2 = sqrt(sqr(cir1.r)-sqr(d));
point mid = cir1.c + (cir2.c-cir1.c).unit() * d;
point v = rotate(cir2.c-cir1.c,PI/2).unit()*d2;
p1 = mid + v,p2 = mid -v;
}
point calc(const circle &cir,double angle)
{
point p = point (cir.c.x+cir.r,cir.c.y);
return rotate(p,angle,cir.c);
}
circle cir[N];
bool del[N];
int n;
double solve()
{
double ans = 0 ;
for ( int i = 0 ; i < n ; i++){
for ( int j = 0 ; j < n ; j++) if (!del[j]){
if (i==j) continue;
if (cir[j].contain(cir[i]))
{ del[i] = true;
break;
}
}
}
for ( int i = 0 ; i < n ; i++) if (!del[i]){
circle &mc = cir[i];
point p1,p2;
bool flag = false;
for ( int j = 0 ; j < n ; j++) if (!del[j]){
if (i==j) continue;
if (!mc.interect(cir[j])) continue;
flag = true;
intersection(mc,cir[j],p1,p2);
double rs = (p2-mc.c).angle(),rt = (p1-mc.c).angle();
if (dblcmp(rs)<0) rs+=2*PI;
if (dblcmp(rt)<0) rt+=2*PI;
if (dblcmp(rs-rt)>0) mc.add(region(rs,PI*2)),mc.add(region(0,rt));
else mc.add(region(rs,rt));
}
if (!flag) { ans += PI*sqr(mc.r); continue;}
sort(mc.reg.begin(),mc.reg.end());
int cnt = 1;
for ( int j = 1 ; j < mc.reg.size() ; j++)
{
if (dblcmp(mc.reg[cnt-1].ed - mc.reg[j].st)>=0)
mc.reg[cnt-1].ed = max(mc.reg[cnt-1].ed,mc.reg[j].ed);
else mc.reg[cnt++] = mc.reg[j];
}
mc.add(region());
mc.reg[cnt]=mc.reg[0];
for ( int j = 0 ; j < cnt ; j++)
{
p1 = calc(mc,mc.reg[j].ed);
p2 = calc(mc,mc.reg[j+1].st);
ans +=cross(p1,p2)/2;
double angle = mc.reg[j+1].st - mc.reg[j].ed;
if (dblcmp(angle)<0) angle+=2*PI;
ans+=0.5*sqr(mc.r)*(angle-sin(angle));
}
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif
scanf("%d",&n);
for ( int i = 0 ; i < n ; i++) cir[i].input();
printf("%.5f\n",solve());
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}