HAOI2008 下落的圆盘（计算几何）

发表于 |
字数统计: 813字 | 阅读时长 ≈ 4min

【HAOI2008】下落的圆盘

问题描述

有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.

输入格式

第一行为1个整数n,N<=1000

接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.

输出格式

最后的周长，保留三位小数

样例输入 1

2

1 0 0

1 1 0

样例输出 1

10.472

样例输入 2

6

9.960 -10.180 19.140

4.370 -3.500 18.740

9.030 -8.060 -12.500

3.830 -14.160 -16.940

7.190 -5.860 8.260

7.270 8.900 17.720

样例输出 2

229.401

这道题比较好像，直接从前往后依次讨论每个圆对答案的贡献，就枚举一下在他后面的圆，然后算一下圆交，得到两个交点之间的弧度，然后把所有的这些弧度区间拿来做线段覆盖就好了，注意处理相离和内含。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#define N 2005
using namespace std;
const double pi=4.0*atan(1.0);
struct node{double x,y;};
struct circle{node o;double r;}C[N];
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
node operator*(node a,double k){return (node){a.x*k,a.y*k};}
node operator/(node a,double k){return (node){a.x/k,a.y/k};}
bool operator<(node a,node b)
{
	if(a.x==b.x)return a.y>b.y;
	return a.x<b.x;
}
int n;
double dis(node a,node b)
{
	double x=a.x-b.x;
	double y=a.y-b.y;
	return sqrt(x*x+y*y);
}
bool Cover(circle a,circle b)
{
	if(a.r>b.r)return 0;
	return dis(a.o,b.o)<=b.r-a.r;
}
bool Apart(circle a,circle b)
{
	return dis(a.o,b.o)>=a.r+b.r;
}
node Get(circle a,circle b)
{
	double d=dis(a.o,b.o);
	double Cos=(a.r*a.r+d*d-b.r*b.r)/(2.0*a.r*d);
	double Sin=sqrt(1.0-Cos*Cos);
	node v=b.o-a.o,w=(node){-v.y,v.x};
	v=v/d;w=w/d;v=v*(a.r*Cos);w=w*(a.r*Sin);
	node p1=a.o+v+w,p2=a.o+v-w;
	node v1=p1-a.o,v2=p2-a.o;
	return (node){atan2(v2.y,v2.x),atan2(v1.y,v1.x)};
}
double Cal(int t)
{
	int i,j,k;vector<node>S;
	for(i=t+1;i<=n;i++)
	{
		if(Cover(C[t],C[i]))return 0;
		if(Cover(C[i],C[t]))continue;
		if(Apart(C[i],C[t]))continue;
		node tmp=Get(C[t],C[i]);
		if(tmp.x<tmp.y)S.push_back(tmp);
		else S.push_back((node){tmp.x,pi}),S.push_back((node){-pi,tmp.y});
	}
	sort(S.begin(),S.end());
	double l=-pi,r=-pi,ans=0;
	for(i=0;i<S.size();i++)
	{
		if(S[i].x>r)ans+=r-l,l=S[i].x,r=S[i].y;
		else if(S[i].y>r)r=S[i].y;
	}
	return (2*pi-ans-r+l)*C[t].r;
}
int main()
{
	int i,j,k;double r,x,y,Ans=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lf%lf%lf",&r,&x,&y);
		C[i]=(circle){(node){x,y},r};
	}
	for(i=1;i<=n;i++)Ans+=Cal(i);
	printf("%.3lf",Ans);
}