1043: [HAOI2008]下落的圆盘 - BZOJ

时间：2020-12-06 00:53:31

Description
1043: [HAOI2008]下落的圆盘 - BZOJ
有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π里

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

 

1043: [HAOI2008]下落的圆盘 - BZOJ1043: [HAOI2008]下落的圆盘 - BZOJ
  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
 29     begin
 30       if y>-eps then exit(pi/2)
 31       else exit(pi*3/2);
 32     end;
 33     if abs(y)<eps then
 34     begin
 35       if x>-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 do
 65         inc(i);
 66       while ll[j]>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<r then sort(i,r);
 77     if l<j then sort(l,j);
 78 end;
 79 
 80 procedure work;
 81 var
 82     i,j:longint;
 83     d,a,b,sum,xx,yy:double;
 84     cover:boolean;
 85 begin
 86     for i:=1 to n do
 87       begin
 88         tot:=0;
 89         cover:=false;
 90         for j:=i+1 to n do
 91           begin
 92             d:=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
 93             if (r[i]+r[j]-d<eps)or(d+r[j]-r[i]<eps) then continue;
 94             if d+r[i]-r[j]<eps then
 95             begin
 96               cover:=true;
 97               break;
 98             end;
 99             a:=tan(x[j]-x[i],y[j]-y[i]);
100             b:=angle(d,r[i],r[j]);
101             inc(tot);
102             ll[tot]:=a-b;
103             rr[tot]:=a+b;
104             if ll[tot]<-eps then
105             begin
106               ll[tot+1]:=2*pi+ll[tot];
107               rr[tot+1]:=2*pi;
108               ll[tot]:=0;
109               inc(tot);
110             end;
111             if rr[tot]>2*pi+eps then
112             begin
113               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 do
128           if ll[j]+eps<=yy then
129           begin
130             if rr[j]+eps<=yy then continue;
131             yy:=rr[j];
132           end
133           else
134           begin
135             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 begin
145     init;
146     work;
147 end.
View Code

 

标签：

相关文章