【BZOJ】1043: [HAOI2008]下落的圆盘（计算几何基础+贪心）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

const double PI=acos(-1), eps=1e-6;
int dcmp(double x) { return abs(x)<eps?0:(x<0?-1:1); }
struct ipt { double x, y; ipt(double _x=0, double _y=0) : x(_x), y(_y) {} };
struct icir { ipt x; double r; };
typedef ipt ivt;
ivt operator- (ipt &a, ipt &b) { return ivt(a.x-b.x, a.y-b.y); }
double iangle(ivt v) { return atan2(v.y, v.x); }
double sqr(double x) { return x*x; }
double dis(ipt &a, ipt &b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }

bool getCC(icir &a, icir &b, double &ang1, double &ang2) {
	static double d, ang;
	d=dis(a.x, b.x);
	if(dcmp(d)==0) return false;
	if(dcmp(a.r+b.r-d)<=0) return false;
	if(dcmp(a.r-b.r-d)>=0) return false;
	ang=iangle(b.x-a.x);
	double da=acos((sqr(d)+sqr(a.r)-sqr(b.r))/a.r/d/2);
	ang1=ang-da; //dbg(da);
	ang2=ang+da;
	return true;
}

const int N=1005;
int n;
icir a[N];
struct dat { double l, r; }line[N*2];
bool cmp(const dat &a, const dat &b) { return a.l==b.l?a.r>b.r:a.l<b.l; }

double work(int now) {
	int ln=0;
	static double ang1, ang2;
	for1(i, now+1, n) { double d=dis(a[now].x, a[i].x); if(dcmp(a[i].r-a[now].r-d)>=0) return 0; } //puts("here");
	for1(i, now+1, n) {
		if(getCC(a[now], a[i], ang1, ang2)==false) continue;
		if(ang1<0) ang1+=PI*2;
		if(ang2<0) ang2+=PI*2;
		if(dcmp(ang1-ang2)>0) {
			++ln; line[ln].l=0; line[ln].r=ang2;
			++ln; line[ln].l=ang1; line[ln].r=PI*2;
		}
		else { ++ln; line[ln].l=ang1; line[ln].r=ang2; }
	}
	sort(line+1, line+1+ln, cmp);
	double w=0, mx=0;
	for1(i, 1, ln) {
		if(dcmp(mx-line[i].r)>=0) continue;
		mx=max(mx, line[i].l);
		w+=line[i].r-mx;
		mx=max(mx, line[i].r);
	}
	return a[now].r*(PI*2-w);
}

int main() {
	read(n);
	for1(i, 1, n) scanf("%lf%lf%lf", &a[i].r, &a[i].x.x, &a[i].x.y);
	double ans=0;
	for1(i, 1, n) ans+=work(i);
	printf("%.3f\n", ans);
	return 0;
}