poj1688

2018年01月15日 ⁄ 综合 ⁄ 共 4764字 ⁄ 字号 评论关闭

【题意】

【输入】

【输出】

Sample Input

```2
4
100 100 20
100 135 20
135 100 20
135 135 20
1
10 10 40
```

Sample Output

```1
0
```

07年论文有讲（高逸涵《与圆有关的离散化方法》）

```program poj1688;
const
esp:extended=1e-8;
type
line=record
l,r:extended;
end;
node=record
x:extended;
incr:boolean;
end;
var
n,i,j,k,w,t,tot,all,total,o,ans,xx,oo,count:longint;
x,y,r:array [0..21] of longint;
event:array [0..601] of extended;
xl:array [0..61] of node;
temp:node;
ind:array [0..10001] of line;
own:array [0..10001] of longint;
sum:array [0..1] of longint;
dl:array [0..1,0..10001] of longint;
yes:array [0..10001]  of boolean;
root,next,point:array [0..10001] of longint;

procedure swap_int (var a,b:longint);
var
i:longint;
begin
i:=a;
a:=b;
b:=i;
end;

procedure swap_dou (var a,b:extended);
var
i:extended;
begin
i:=a;
a:=b;
b:=i;
end;

procedure solve (i,j:longint);
var
left,right,t,mid,leftr,rightr:extended;
begin
t:=y[j]+(y[i]-y[j])*r[j]/(r[i]+r[j]);
left:=y[j]-r[j];
if y[i]-r[i]>left then left:=y[i]-r[i];
right:=t;
repeat
mid:=(left+right)/2;
leftr:=sqrt(sqr(r[j])-sqr(mid-y[j]));
rightr:=sqrt(sqr(r[i])-sqr(mid-y[i]));
if (x[j]+leftr<x[i]-rightr) or (x[j]-leftr>x[i]+rightr) then
left:=mid
else
right:=mid;
until abs(left-right)<1e-8;
inc(tot);
event[tot]:=left;

left:=t;
right:=y[j]+r[j];
if y[i]+r[i]<right then right:=y[i]+r[i];
repeat
mid:=(left+right)/2;
leftr:=sqrt(sqr(r[j])-sqr(mid-y[j]));
rightr:=sqrt(sqr(r[i])-sqr(mid-y[i]));
if (x[j]+leftr<x[i]-rightr) or (x[j]-leftr>x[i]+rightr) then
right:=mid
else
left:=mid;
until abs(left-right)<1e-8;
inc(tot);
event[tot]:=left;
end;

procedure qsort (s,e:longint);
var
i,j:longint;
k:extended;
begin
if s>=e then exit;
i:=s;
j:=e;
k:=event[(s+e) div 2];
while i<=j do
begin
while (i<=j)and(event[i]<k) do inc(i);
while (i<=j)and(event[j]>k) do dec(j);
if i>j then break;
swap_dou(event[i],event[j]);
inc(i);
dec(j);
end;
qsort(s,j);
qsort(i,e);
end;

procedure connect (s,e:longint);
begin
inc(oo);
point[oo]:=e;
next[oo]:=root[s];;
root[s]:=oo;
end;

procedure dfs (now:longint);
var
i:longint;
begin
yes[now]:=true;
i:=root[now];
while i<>0 do
begin
if not yes[point[i]] then
begin
own[point[i]]:=own[now];
if point[i]>=dl[o,1] then inc(count);
dfs(point[i]);
end;
i:=next[i];
end;
end;

procedure merge (now:longint);
var
i,j,k:longint;
a,b,t:extended;
begin
o:=1-o;
t:=event[now]-esp;
total:=0;
for i:=1 to n do
if sqr(y[i]-t)<sqr(r[i]) then
begin
inc(total);
xl[total].x:=x[i]-sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=true;
inc(total);
xl[total].x:=x[i]+sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=false;
end;
for i:=1 to total-1 do
for j:=i+1 to total do
if xl[i].x>xl[j].x then
begin
temp:=xl[i];
xl[i]:=xl[j];
xl[j]:=temp;
end;
k:=0;
w:=1;
for i:=1 to total do
if xl[i].incr then
begin
if k=0 then
begin
ind[dl[1-o,w]].r:=xl[i].x;
inc(w);
end;
inc(k);
end
else
begin
dec(k);
if k=0 then ind[dl[1-o,w]].l:=xl[i].x;
end;
t:=event[now]+esp;
total:=0;
for i:=1 to n do
if sqr(y[i]-t)<sqr(r[i]) then
begin
inc(total);
xl[total].x:=x[i]-sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=true;
inc(total);
xl[total].x:=x[i]+sqrt(sqr(r[i])-sqr(y[i]-t));
xl[total].incr:=false;
end;
for i:=1 to total-1 do
for j:=i+1 to total do
if xl[i].x>xl[j].x then
begin
temp:=xl[i];
xl[i]:=xl[j];
xl[j]:=temp;
end;
sum[o]:=1;
inc(all);
dl[o,1]:=all;
ind[all].l:=-1000000;
k:=0;
for i:=1 to total do
if xl[i].incr then
begin
if k=0 then ind[all].r:=xl[i].x;
inc(k);
end
else
begin
dec(k);
if k=0 then
begin
inc(all);
inc(sum[o]);
dl[o,sum[o]]:=all;
ind[all].l:=xl[i].x;
end;
end;
ind[all].r:=1000000;
for i:=1 to sum[o] do
yes[dl[o,i]]:=false;
for i:=1 to sum[1-o] do
yes[dl[1-o,i]]:=false;
for i:=1 to sum[1-o] do
root[dl[1-o,i]]:=0;
oo:=0;
for i:=1 to sum[1-o] do
for j:=1 to sum[1-o] do
if (i<>j)and(own[dl[1-o,i]]=own[dl[1-o,j]]) then
begin
connect(dl[1-o,i],dl[1-o,j]);
connect(dl[1-o,j],dl[1-o,i]);
end;
for i:=1 to sum[1-o] do
for j:=1 to sum[o] do
if not ((ind[dl[1-o,i]].l>ind[dl[o,j]].r)or(ind[dl[1-o,i]].r<ind[dl[o,j]].l)) then
begin
connect(dl[1-o,i],dl[o,j]);
connect(dl[o,j],dl[1-o,i]);
end;
for i:=1 to sum[1-o] do
if not yes[dl[1-o,i]] then
begin
count:=0;
dfs(dl[1-o,i]);
if count=0 then inc(ans);
end;
for i:=1 to sum[o] do
if not yes[dl[o,i]] then
begin
inc(xx);
own[dl[o,i]]:=xx;
end;
end;

begin
while t<>0 do
begin
fillchar(root,sizeof(root),false);
fillchar(next,sizeof(next),0);
for i:=1 to n do
for i:=1 to n-1 do
for j:=i+1 to n do
if x[i]-r[i]>x[j]-r[j] then
begin
swap_int(x[i],x[j]);
swap_int(y[i],y[j]);
swap_int(r[i],r[j]);
end;
tot:=0;
for i:=1 to n do
begin
inc(tot);
event[tot]:=y[i]-r[i];
inc(tot);
event[tot]:=y[i]+r[i];
end;
for i:=1 to n-1 do
for j:=i+1 to n do
if sqr(x[i]-x[j])+sqr(y[i]-y[j])<sqr(r[i]+r[j]) then
solve(i,j);
qsort(1,tot);
event[0]:=-10000000000;
o:=0;
sum[o]:=1;
all:=1;
ans:=0;
xx:=1;
dl[o,1]:=1;
own[1]:=1;
ind[1].l:=-1000000;
ind[1].r:=1000000;
for i:=1 to tot do
if event[i]-event[i-1]>esp then
merge(i);
writeln(ans);
dec(t);
end;
end.
```
【上篇】
【下篇】