Description

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

Input

n ri xi y1 ... rn xn yn

Output

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

Sample Input

2

1 0 0

1 1 0

Sample Output

10.472

数据规模

n<=1000

 

 

调了一晚上外加下午（弱菜写计算几何，tan函数都抄错了）

对每一个圆计算覆盖区间，然后排序，再区间合并，注意范围，我是全部弄到0到2π里

再膜拜一下，最后还是他看出错误来的

 

1 uses math;  2 const  3     maxn=1010;  4     eps=1e-7;  5 var  6     r,x,y,ll,rr:array[0..maxn*2]of double;  7     n,tot:longint;  8     ans:double;  9  10 procedure init; 11 var 12     i:longint; 13 begin 14     read(n); 15     for i:=1 to n do 16       read(r[i],x[i],y[i]); 17 end; 18  19 function angle(a,b,c:double):double; 20 begin 21     exit(arccos((a*a+b*b-c*c)/(2*a*b))); 22 end; 23  24 function tan(x,y:double):double; 25 var 26     a:double; 27 begin 28     if abs(x)
      
       -eps then exit(pi/2) 31       else exit(pi*3/2); 32     end; 33     if abs(y)
       
        -eps then exit(0) 36       else exit(pi); 37     end; 38     a:=arctan(y/x); 39     if a<-eps then a:=-a; 40     if x>-eps then 41       if y>-eps then exit(a) 42       else exit(2*pi-a) 43     else 44       if y>-eps then exit(pi-a) 45       else exit(pi+a); 46 end; 47  48 procedure swap(var x,y:double); 49 var 50     t:double; 51 begin 52     t:=x;x:=y;y:=t; 53 end; 54  55 procedure sort(l,r:longint); 56 var 57     i,j:longint; 58     y:double; 59 begin 60     i:=l; 61     j:=r; 62     y:=ll[(l+r)>>1]; 63     repeat 64       while ll[i]+eps
        
         y+eps do 67         dec(j); 68       if i<=j then 69       begin 70         swap(ll[i],ll[j]); 71         swap(rr[i],rr[j]); 72         inc(i); 73         dec(j); 74       end; 75     until i>j; 76     if i
         
          2*pi+eps then112             begin113               rr[tot+1]:=rr[tot]-2*pi;114               ll[tot+1]:=0;115               rr[tot]:=2*pi;116               inc(tot);117             end;118           end;119         if cover then continue;120         sort(1,tot);121         inc(tot);122         ll[tot]:=100;123         rr[tot]:=100;124         sum:=0;125         xx:=0;126         yy:=0;127         for j:=1 to tot do128           if ll[j]+eps<=yy then129           begin130             if rr[j]+eps<=yy then continue;131             yy:=rr[j];132           end133           else134           begin135             sum:=sum+yy-xx;136             xx:=ll[j];137             yy:=rr[j];138           end;139         ans:=ans+(2*pi-sum)*r[i];140       end;141     write(ans:0:3);142 end;143 144 begin145     init;146     work;147 end.