【bzoj1043】[HAOI2008]下落的圆盘

2014年11月30日3,3465

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
对圆弧做贪心线段覆盖,得到每个圆对答案的贡献

 

 

  • Platypus2015年1月24日 下午6:06 回复

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

    #1  
  • HouJikan2015年4月16日 上午8:38 回复

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

    #2  
    • hzwer2015年4月16日 上午8:54 回复
      admin

      atan2(对边,邻边) 我的代码中计算的是a->b圆心连线的倾角(竖直向下为0度)

      #21
    • Loading2016年6月2日 下午4:29 回复

      两种效果一样的TT

      #21
  • mps2016年8月1日 下午9:16 回复

    QAQ学长图挂了

    #3