BZOJ-1043 [HAOI2008]下落的圆盘

几何题。。。

先把所有圆储存起来，然后对于每个圆我们求得之后放下的圆挡住了的部分，求个并集，并把没被挡到的周长加进答案。

#include <cstdlib>

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#define rep(i, l, r) for(int i=l; i<=r; i++)

#define pi acos(-1)

#define maxn 1234

typedef long long ll;

using namespace std;

inline int read()

{

	int x=0, f=1; char ch=getchar();

	while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}

	while (isdigit(ch)) x=x*10+ch-'0', ch=getchar();

	return x*f;

}

struct line{double l, r;} q[maxn*2];

bool cmp(line a, line b){return a.l<b.l || (a.l==b.l && a.r<b.r);}

double r[maxn], x[maxn], y[maxn];

double dis(int a, int b){return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));}

int main()

{

	int n=read(); double ans=0;

	rep(i, 1, n) scanf("%lf%lf%lf", &r[i], &x[i], &y[i]);

	rep(a, 1, n)

	{

		int top=0;

		bool end=0; rep(b, a+1, n) if (r[a]+dis(a, b)<=r[b]) end=1; if (end) continue;

		rep(b, a+1, n) if (r[b]+dis(a, b)>r[a] && r[a]+r[b]>dis(a, b))

		{

			double r1=r[a], r2=r[b], d=dis(a, b), t, v;

			t=acos((r1*r1-r2*r2+d*d)/(2*d)/r1);

			v=atan2((x[a]-x[b]),(y[a]-y[b]));

			q[++top]=(line){v-t, v+t};

		}

		rep(i, 1, top)

		{

			if (q[i].l<0) q[i].l+=2*pi;

			if (q[i].l>2*pi) q[i].l-=2*pi;

			if (q[i].r<0) q[i].r+=2*pi;

			if (q[i].r>2*pi) q[i].r-=2*pi;

			if (q[i].l>q[i].r)

				q[++top]=(line){0,q[i].r}, q[i].r=2*pi;

		}

		sort(q+1, q+top+1, cmp);

		double now=0, tmp=0;

		rep(i, 1, top)

		{

			if (q[i].l>now) tmp+=q[i].l-now;

			now=max(now, q[i].r);

		}

		tmp+=2*pi-now;

		ans+=tmp*r[a];

	}

	printf("%.3lf\n", ans);

	return 0;

}