「BZOJ1043」[HAOI2008] 下落的圆盘

2014年11月30日4,2245

Description

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

Input

n ri xi y1 … rn xn yn

Output

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

Sample Input

2
1 0 0
1 1 0

Sample Output

10.472

HINT

数据规模
n<=1000

题解

 每个圆被其它每个圆盖住的部分是一段圆弧
求出这段圆弧
这图是不是很丑TAT。。。
根据r1^2-x^2=r2^2-(d-x)^2
得x=(r2^2-r1^2+d^2)/(2*d)
通过x和反三角函数就能算出弧的夹角,以及弧的左右端点角度,0<=l,r<=2*pi
对圆弧做贪心线段覆盖,得到每个圆对答案的贡献

 

 

说点什么

提醒
avatar
mps

QAQ学长图挂了

HouJikan
HouJikan

黄学长可以请问一下为什么35行atan2里面用的是(x,y)吗。。不管怎么看都应该是(y,x)但是总是不对TAT。。改成(x,y)就对了

Loading

两种效果一样的TT

Platypus
Platypus

根据r1^2-x^2=r1^2-(d-x)^2 应该改成
根据r1^2-x^2=r2^2-(d-x)^2