{ tde } {$APPTYPE CONSOLE} {$B-,R-,O+} { Швидкий розв'язок задачі CIRCLES. O(n log n) } const maxn=10000; type circle=record x,y,r:longint; end; event=record index:smallint; x,y:smallint; op:smallint; end; tnode=record index:smallint; parent,left,right:smallint; end; var fi,fo:text; n,i,j,k,r:smallint; a:array[1..maxn] of circle; e:array[1..2*maxn] of event; tree:array[1..maxn] of tnode; h,root:smallint; procedure Answer(i,j:smallint); begin writeln(fo,i,' ',j); close(fi); close(fo); halt; end; procedure Sort(l,r:smallint); var i,j:smallint; k,x:event; begin if(lk.y)or((e[j].y=k.y)and(e[j].op>k.op)))do dec(j); if(i<=j)then begin x:=e[i]; e[i]:=e[j]; e[j]:=x; inc(i); dec(j); end; until i>j; Sort(l,j); Sort(i,r); end; end; function Intersect(i,j:smallint):boolean; var d:longint; begin d:=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y); Intersect:=(sqr(a[i].r+a[j].r)>=d)and(sqr(a[i].r-a[j].r)<=d); end; function insert(index:smallint):smallint; var tek:smallint; begin if(root=0)then begin inc(h); tree[h].index:=index; insert:=h; root:=h; exit; end; tek:=root; while not{((a[index].x=a[tree[tek].index].x)or} (((a[index].xa[tree[tek].index].x)and(tree[tek].right=0))or ((a[index].x=a[tree[tek].index].x)and(a[index].y+a[index].r>a[tree[tek].index].x+a[tree[tek].index].r)and(tree[tek].right=0)))do begin if(a[index].x=a[tree[tek].index].x)and(Intersect(index,tree[tek].index))then Answer(index,tree[tek].index); if(a[index].xindex)do if(a[index].x0)do tek:=tree[tek].right; ans:=tek; end; {if (ans=0)and(not(a[tree[ans].index].x0)do tek:=tree[tek].left; ans:=tek; end; {if (ans=0)or(not(a[tree[ans].index].x>a[tree[node].index].x))then ans:=0;} right_neightbour:=ans; end; procedure erase(node:smallint); var tek:smallint; begin if(tree[node].left=0)and(tree[node].right=0)then begin if(tree[node].parent<>0)then begin if(tree[tree[node].parent].left=node)then tree[tree[node].parent].left:=0 else tree[tree[node].parent].right:=0; end else root:=0; end else if(tree[node].left=0)then begin if(node=root)then begin root:=tree[node].right; tree[tree[node].right].parent:=0; end else begin tree[tree[node].right].parent:=tree[node].parent; if(tree[tree[node].parent].left=node)then tree[tree[node].parent].left:=tree[node].right else tree[tree[node].parent].right:=tree[node].right; end; end else if(tree[node].right=0)then begin if(node=root)then begin root:=tree[node].left; tree[tree[node].left].parent:=0; end else begin tree[tree[node].left].parent:=tree[node].parent; if(tree[tree[node].parent].left=node)then tree[tree[node].parent].left:=tree[node].left else tree[tree[node].parent].right:=tree[node].left; end; end else begin tek:=right_neightbour(node); tree[node].index:=tree[tek].index; erase(tek); end; end; begin assign(fi,'circles.dat'); assign(fo,'circles.sol'); reset(fi); rewrite(fo); readln(fi,n); for i:=1 to n do readln(fi,a[i].x,a[i].y,a[i].r); for i:=1 to n do begin e[2*i-1].index:=i; e[2*i-1].y:=a[i].x; e[2*i-1].y:=a[i].y-a[i].r; e[2*i-1].op:=0; e[2*i].index:=i; e[2*i].y:=a[i].x; e[2*i].y:=a[i].y+a[i].r; e[2*i].op:=1; end; Sort(1,2*n); fillchar(tree,sizeof(tree),0); h:=0; root:=0; for i:=1 to 2*n do if(e[i].op=0)then begin if(i=10921)then begin j:=1; if(j=2)then; end; j:=insert(e[i].index); k:=left_neightbour(j); if(k<>0)and(Intersect(e[i].index,tree[k].index))then Answer(e[i].index,tree[k].index); k:=right_neightbour(j); if(k<>0)and(Intersect(e[i].index,tree[k].index))then Answer(e[i].index,tree[k].index); end else begin r:=find(e[i].index); j:=left_neightbour(r); if(j<>0)then j:=tree[j].index; k:=right_neightbour(r); if(k<>0)then k:=tree[k].index; erase(r); if(j<>0)and(k<>0)and(j<>k)and(Intersect(j,k))then Answer(j,k); end; writeln(fo,0); close(fi); close(fo); end.