program voronoi_dc; const maxn=200; zero=1e-7; type point=record x,y:double; k:longint; end; edge=^Tedge; Tedge=record x:longint; next:edge; end; var way:array[1..maxn,1..maxn]of boolean; used,a:array[1..maxn]of longint; check:array[1..maxn]of boolean; e_free:array[1..maxn*maxn]of edge; p:array[1..maxn]of point; v:array[1..maxn]of edge; tot,m,n:longint; procedure sort(l,r:longint); var t:point; x,y:double; i,j:longint; begin x:=p[(l+r) div 2].x; y:=p[(l+r) div 2].y; i:=l;j:=r; while true do begin while (p[i].xx)or((p[j].x=x)and(p[j].y>y)) do dec(j); if j>i then begin t:=p[i]; p[i]:=p[j]; p[j]:=t; inc(i);dec(j); end else break; end; if j>l then sort(l,j); if j0 then p.x:=(-c2-b2*p.y)/a2; end; if a2=0 then begin p.y:=-c2/b2; if a1<>0 then p.x:=(-c1-b1*p.y)/a1; end; end else if (b1=0)or(b2=0) then begin if b1=0 then begin p.x:=-c1/a1; if b2<>0 then p.y:=(-c2-a2*p.x)/b2; end; if b2=0 then begin p.x:=-c2/a2; if b1<>0 then p.y:=(-c1-a1*p.x)/b1; end; end else begin p.x:=(-b2*c1+b1*c2)/(b2*a1-b1*a2); p.y:=(-a2*c1+a1*c2)/(a2*b1-a1*b2); end; end; function get_sit(p1,p2,p3:point):double; begin get_sit:=(p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y); end; procedure get_tang(l,k,r:longint;var p1,p2,p3,p4:longint); var xx,i,tot:longint; begin tot:=2; fillchar(a,sizeof(a),0); fillchar(check,sizeof(check),false); a[1]:=l;a[2]:=l+1;i:=l+2; check[l]:=true;check[l+1]:=true; while i<=r do begin if not check[i] then begin while (tot>1)and(get_sit(p[a[tot-1]],p[a[tot]],p[i])<0) do begin check[a[tot]]:=false; a[tot]:=0; dec(tot); end; inc(tot); check[i]:=true; a[tot]:=i; end; inc(i); end; for i:=1 to tot do if a[i]>k then break; p1:=a[i-1];p2:=a[i]; xx:=tot; for i:=a[tot] downto l do if not check[i] then begin check[i]:=true; inc(tot); a[tot]:=i; break; end; while i>=a[1] do begin if (not check[i])or(i=a[1]) then begin while (tot>xx)and(get_sit(p[a[tot-1]],p[a[tot]],p[i])<0) do begin check[a[tot]]:=false; a[tot]:=0; dec(tot); end; inc(tot); check[i]:=true; a[tot]:=i; end; dec(i); end; for i:=tot downto 1 do if a[i]>k then break; p4:=a[i];p3:=a[i+1]; end; procedure set_memory; var i:longint; begin m:=n*n; for i:=1 to m do new(e_free[i]); end; function get_memory:edge; begin dec(m); get_memory:=e_free[m+1]; end; procedure add_edge(x,y:longint); var e:edge; begin if way[x,y] then exit; e:=get_memory; e^.next:=v[x]; e^.x:=y; v[x]:=e; way[x,y]:=true; end; function get_dis(a,b:point):double; begin get_dis:=sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); end; procedure del_edge(x,y:longint); var ee,e:edge; begin way[x,y]:=false; e:=v[x]; if e^.x=y then v[x]:=e^.next else begin while e^.next^.x<>y do e:=e^.next; ee:=e; e:=e^.next; ee^.next:=e^.next end; inc(m); e_free[m]:=e; end; function get_three(a,b,c:point):point; var p1,p2,p3,p4,p:point; begin get_bis(a,b,p1,p2); get_bis(c,a,p3,p4); if not get_inter(p1,p2,p3,p4,p) then p.y:=1e100; get_three:=p; end; procedure del_all(a,b,c,pd,l,r:longint); var e:edge; x:longint; begin e:=v[a]; while e<>nil do if (get_sit(p[b],p[c],p[e^.x])*pd<0)and(e^.x<>b)and(get_sit(p[a],p[b],p[e^.x])*pd>0)and(e^.x>=l)and(e^.x<=r) then begin x:=e^.x; e:=e^.next; del_edge(a,x); del_edge(x,a); end else e:=e^.next; end; procedure merge(min,mid,max:longint); var q3,q4,pd,qq2,qq1,q1,q2:longint; p1,p2,pp1,pp2,pp:point; e:edge; begin fillchar(used,sizeof(used),0); get_tang(min,mid,max,q1,q2,q3,q4); qq1:=0;qq2:=0; add_edge(q1,q2); add_edge(q2,q1); add_edge(q3,q4); add_edge(q4,q3); while true do begin get_bis(p[q1],p[q2],p1,p2); pd:=0;pp.y:=1e100; e:=v[q1]; while e<>nil do begin if (e^.x>=min)and(e^.x<=mid) then pp1:=get_three(p[q1],p[q2],p[e^.x]) else pp1.y:=1e101; if ((used[q2]=0)or(get_sit(p[q2],p[used[q2]],p[e^.x])<0))and(get_sit(p[q2],p[q1],p[e^.x])<0)and((pp1.ynil do begin if e^.x>mid then pp2:=get_three(p[q1],p[q2],p[e^.x]) else pp2.y:=1e101; if ((used[q1]=0)or(get_sit(p[q1],p[used[q1]],p[e^.x])>0))and(get_sit(p[q1],p[q2],p[e^.x])>0)and((pp2.ynil do begin if e^.x>i then begin writeln(p[i].k-1,' ',p[e^.x].k-1); inc(tot); end; e:=e^.next; end; end; writeln(tot); end; begin assign(input,'voronoi.in');reset(input); assign(output,'voronoi.out');rewrite(output); init; set_memory; build_vor(1,n); print; close(input);close(output); end.