Qalaysan

Please, post some tests...

I think that's why my program gets WA at 3. Otherwise it should work, since we're dealing with integer values.

I cannot find to my mistake!!! At me a problem with third the test
Here my algorithm:
  1. I write down minimal a distance from a point up to a square:
    Whether I look the point in a square, that is when the answer 0 lays. Here I used vectors! If the point does not lay in a square I make it: I Search for a straight line which lays more close to the given point. Then I create a triangle and I search for height of this triangle. Whether but I look all corners at a basis of a triangle blunt if is not present I choose the minimal distance from given to a point up to points of a straight line.
2. I sort

Here my algorithm, in what a problem? Help!!!

{$N+}
type kor=record
       x,y:longint;
    end;
var
m:array[1..100,1..4]of kor;
Sort:array[1..100]of byte;
l:array[1..100]of longint;
t:kor;
l1,max:longint;
j,i,n,tmp:byte;

procedure Swep(var a,b:byte);
begin  tmp:=a; a:=b; b:=tmp;   end;

begin
readln(n);
for i:=1 to n do
  begin
    readln(m[i,1].x,m[i,1].y,m[i,2].x,m[i,2].y);
    if m[i,1].x>m[i,2].x then
       begin
        t.x:=m[i,1].x;
        m[i,1].x:=m[i,2].x;
        m[i,2].x:=t.x;
       end;

    if m[i,1].y>m[i,2].y then
       begin
        t.y:=m[i,1].y;
        m[i,1].y:=m[i,2].y;
        m[i,2].y:=t.y;
       end;

    m[i,3].x:=m[i,1].x;
    m[i,3].y:=m[i,2].y;
    m[i,4].x:=m[i,2].x;
    m[i,4].y:=m[i,1].y;
  end;

readln(t.x,t.y);

for i:=1 to n do
  begin
   max:=2147483647;
    for j:=1 to 4 do
       begin
         l1:=sqr(m[i,j].x-t.x)+sqr(m[i,j].y-t.y);
         if max>l1 then max:=l1;
       end;

   if (t.y>m[i,1].y)and(t.y<m[i,4].y)and(max>abs(m[i,1].x-t.x)) then max:=sqr(m[i,1].x-t.x);
   if (t.y>m[i,3].y)and(t.y<m[i,2].y)and(max>abs(m[i,2].x-t.x)) then max:=sqr(m[i,2].x-t.x);

   if (t.x>m[i,4].x)and(t.x<m[i,2].x)and(max>abs(m[i,2].y-t.y)) then max:=sqr(m[i,2].y-t.y);
   if (t.x>m[i,1].x)and(t.x<m[i,3].x)and(max>abs(m[i,3].y-t.y)) then max:=sqr(m[i,3].y-t.y);

   if (t.x>=m[i,1].x)and(t.x<=m[i,2].x)and(t.y>=m[i,1].y)and(t.y<=m[i,2].y) then max:=0;

   l[i]:=max;
  end;

for i:=1 to n do sort[i]:=i;

for i:=1 to n do
 for j:=1 to n-1 do
   begin
   if l[sort[j]]>l[sort[j+1]] then swep(sort[j],sort[j+1]);
   if (l[sort[j]]=l[sort[j+1]])and(sort[j]>sort[j+1]) then swep(sort[j],sort[j+1]);

   end;

for i:=1 to n do  write(sort[i],' ');

end.


HELP!!!!!!!!!

I got WA at test 3 many times and I found that the sort method was wrong... I used selection sort for the distances but when they were equal I didn't veryfied that the indexes are ascending... Maybe this will help somebody...

I have seen postts before, but I can0t understand why my code is wrong!
plz if someone can give me some hint I would appreciate very much
here is my code:

#include <stdio.h>
double x[103],y[103],x2[103],y2[103],xp,yp;
int vx[5],vy[5],d[103],ord[103];

swap(int a, int b){
    int tmp=d[a],tmp2=ord[a];
    d[a]=d[b];ord[a]=ord[b];
    d[b]=tmp;ord[b]=tmp2;
}

sort(int n){
    int i,j;
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        if(d[i]<d[j]) swap(i,j);
}

calc_v(int n){
   if(x[n]<x2[n]){
        vx[1]=vx[3]=x[n];
        vx[2]=vx[4]=x2[n];
   }
   else if (x[n]>=x2[n]){
        vx[1]=vx[3]=x2[n];
        vx[2]=vx[4]=x[n];
   }
   if(y[n]<y2[n]){
        vy[1]=vy[2]=y[n];
        vy[3]=vy[4]=y2[n];
   }
   else if (y[n]>=y2[n]){
        vy[1]=vy[2]=y2[n];
        vy[3]=vy[4]=y[n];
   }
}

dist(int n){
    if(xp>=vx[1] && xp<=vx[2]){
        if(yp>vy[3]) d[n]=abs(yp-vy[3]);
        else if (yp<vy[1]) d[n]=abs(vy[1]-yp);
        else d[n]=0;
    }
    else if(yp>=vy[1] && yp<=vy[3]){
        if(xp>vx[2]) d[n]=abs(xp-vx[2]);
        else if (xp<vx[1]) d[n]=abs(vx[1]-xp);
        else d[n]=0;
    }
    else{
      if(xp<vx[1]){
        if(yp<vy[1]) d[n]=sqrt(abs(xp-vx[1])*abs(xp-vx[1]) + abs(vy[1]-yp)*abs(vy[1]-yp));
        else if (yp>=vy[3])    d[n]=sqrt(abs(xp-vx[3])*abs(xp-vx[3]) + abs(vy[3]-yp)*abs(vy[3]-yp));
      }
      else if (xp>vx[2]){
            if(yp>vy[4]) d[n]=sqrt(abs(yp-vy[4])*abs(yp-vy[4]) + abs(xp-vx[4])*abs(xp-vx[4]));
            else if (yp<vy[2]) d[n]=sqrt(abs(vy[2]-yp)*abs(vy[2]-yp) + abs(xp-vx[2])*abs(xp-vx[2]));
      }
    }
}

int main()
{
  int n,i;
  scanf("%d",&n);
  for(i=0;i<n;i++)
    scanf("%Lf %Lf %Lf %Lf",&x[i],&y[i],&x2[i],&y2[i]);
  scanf("%Lf %Lf",&xp,&yp);
  for(i=0;i<n;i++){
    calc_v(i);
    dist(i);
  }
  for(i=0;i<n;i++) ord[i]=i;
   sort(n);
   n--;
   for(i=0;i<n;i++)
      printf("%d ",ord[i]+1);
   printf("%d\n",ord[n]+1);
  return 0;
}

// find distance between line Ax,Ay Bx,By and point X,Y
double R(double Ax,double Ay,double Bx,double By){
    double r1,r2;
    double x=(Ax+Bx)/2.0;
    double y=(Ay+By)/2.0;
    do{//(fabs(Ax-Bx)>E1 || fabs(Ay-By)>E1){ -> WA 3
        x=(Ax+Bx)/2.0;
        y=(Ay+By)/2.0;
        r1=len(Ax,Ay,X,Y);
        r2=len(Bx,By,X,Y);
        if(r1>r2){
            Ax=x;
            Ay=y;
        }else{
            Bx=x;
            By=y;
        }
    }while(fabs(r1-r2)>E1);
    return (len(x,y,X,Y));
}
when we find distance between P and some line(Ax Ay Bx By) we must compare r1 and r2!
Sorry for my english.
P.S E1=1.0e-10

{}{$N+}
{}
{}program P1111;
{}
{}{Squares}
{}
{}type Zieve=array[1..4] of record
{----------------------------}x,y:double;
{--------------------------}end;
{}
{}var n:integer;
{----}x0,y0:double;
{----}list:array[1..100] of integer;
{----}l:array[1..100] of double;
{----}cr:array[1..100] of Zieve;
{}
{-}procedure change(var a,b:double);
{}
{-}var c:double;
{}
{-}begin
{}
{---}c:=a;
{---}a:=b;
{---}b:=c;
{}
{-}end;
{}
{-}procedure init;
{}
{-}var i:integer;
{-----}x1,x2,y1,y2:double;
{}
{-}begin
{}
{---}read(n);
{---}for i:=1 to n do
{---}begin
{-----}read(x1,y1,x2,y2);
{-----}if x1>x2 then change(x1,x2);
{-----}if y1>y2 then change(y1,y2);
{-----}cr[i,1].x:=x1;
{-----}cr[i,1].y:=y1;
{-----}cr[i,2].x:=x1;
{-----}cr[i,2].y:=y2;
{-----}cr[i,3].x:=x2;
{-----}cr[i,3].y:=y1;
{-----}cr[i,4].x:=x2;
{-----}cr[i,4].y:=y2;
{---}end;
{---}read(x0,y0);
{}
{-}end;
{}
{-}function long(z:Zieve):double;
{}
{-}var r,min:double;
{-----}i:integer;
{}
{-}begin
{}
{---}if (x0>=z[1].x)and(x0<=z[4].x)and
{------}(y0>=z[1].y)and(y0<=z[4].y) then min:=0 else
{---}begin
{-----}min:=1e+30;
{-----}if (x0>=z[1].x)and(x0<=z[4].x) then
{-----}begin
{-------}r:=sqr(z[1].y-y0);
{-------}if r<min then min:=r;
{-------}r:=sqr(z[4].y-y0);
{-------}if r<min then min:=r;
{-----}end
{-----}else
{-----}if (y0>=z[1].y)and(y0<=z[4].y) then
{-----}begin
{-------}r:=sqr(z[1].x-x0);
{-------}if r<min then min:=r;
{-------}r:=sqr(z[4].x-x0);
{-------}if r<min then min:=r;
{-----}end
{-----}else
{-----}begin
{-------}for i:=1 to 4 do
{-------}begin
{---------}r:=sqr(z[i].x-x0)+sqr(z[i].y-y0);
{---------}if r<min then min:=r;
{-------}end;
{-----}end;
{---}end;
{}
{---}long:=min;
{}
{-}end;
{}
{-}procedure main;
{}
{-}var i,j,k:integer;
{}
{-}begin
{}
{---}for i:=1 to n do
{---}begin
{-----}list[i]:=i;
{-----}l[i]:=long(cr[i]);
{---}end;
{}
{---}for i:=1 to n-1 do
{---}begin
{-----}k:=i;
{-----}for j:=i+1 to n do
{-------}if (l[list[k]]>l[list[j]])or((abs(l[list[k]]-l[list[j]])<1e-14)and(list[k]>list[j])) then k:=j;
{-----}j:=list[k];
{-----}list[k]:=list[i];
{-----}list[i]:=j;
{---}end;
{}
{---}for i:=1 to n do write(list[i],' ');
{}
{-}end;
{}
{}begin
{}
{--}init;
{--}main;
{}
{}end.

Edited by author 28.06.2004 14:01

const
  max   =   100;
  maxC  =   10000;
type
  TRect =   record
              x1, x2, y1, y2 : double;
            end;
var
  n, x0, y0  : Integer;
  R  : array[1..max] of TRect;
  ID : array[1..max] of Integer;
  {*************************}
procedure swap(var i, j : double);
var
  tmp  : double;
begin
  tmp := i; i := j; j := tmp;
end;
  {*************************}
procedure read_f;
var
  i  : Integer;
  x1, x2, y1, y2 : double;
begin
  readln( n);
  for i := 1 to n do
    with R[i] do
      begin
        Id[i] := i;
        readln( x1, y1, x2, y2);
        if x1 > x2 then swap(x1, x2);
        if y1 > y2 then swap(y1, y2);
      end;
  readln( x0, y0);
end;
  {*************************}
function long(x1, y1, x2, y2 : double) : double;
begin
  long := Sqrt(sqr(x1 - x2) + sqr(y1 - y2));
end;
  {*************************}
function inside(i : Integer) : Boolean;
begin
  with R[i] do
    inside := (x0 >= x1) and (x0 <= x2) and (y0 >= y1) and (y0 <= y2);
end;
  {*************************}
function path(i : Integer) : double;
var
  tmp : double;
begin
  if inside(i) then
    begin
      path := 0;
      exit;
    end;
  with R[i] do
    begin
      tmp := 0;
      if (x1 <= x0) and (x0 <= x2) then
        begin
          tmp := maxLongInt;
          if tmp > abs(y0 - y1) then tmp := abs(y0 - y1);
          if tmp > abs(y0 - y2) then tmp := abs(y0 - y2);
          path := tmp; exit;
        end;
      if (y1 <= y0) and (y0 <= y2) then
        begin
          tmp := maxLongInt;
          if tmp > abs(x0 - x1) then tmp := abs(x0 - x1);
          if tmp > abs(x0 - x2) then tmp := abs(x0 - x2);
          path := tmp; exit;
        end;
      tmp := maxLongInt;
      if tmp > long(x1, y1, x0, y0) then tmp := long(x1, y1, x0, y0);
      if tmp > long(x1, y2, x0, y0) then tmp := long(x1, y2, x0, y0);
      if tmp > long(x2, y1, x0, y0) then tmp := long(x2, y1, x0, y0);
      if tmp > long(x2, y2, x0, y0) then tmp := long(x2, y2, x0, y0);
      path := tmp; exit;
    end;
end;
  {*************************}
procedure solve;
var
  i, j, tmp : Integer;
  t1 : double;
begin
  for i := 1 to n do
    for j := i + 1 to n do
      if Path(Id[i]) - Path(Id[j]) > (1e-14) then
        begin
          tmp := Id[i]; Id[i] := Id[j]; Id[j] := tmp;
        end;
end;
  {*************************}
procedure print;
var
  i : Integer;
begin
  for i := 1 to n do write( Id[i], ' ');
end;
  {*************************}
begin
  read_f;
  solve;
  print;
end.

const
  max   =   100;
  maxC  =   10000;
type
  TRect =   record
              x1, x2, y1, y2 : double;
            end;
var
  n, x0, y0  : Integer;
  R  : array[1..max] of TRect;
  ID : array[1..max] of Integer;
  {*************************}
procedure swap(var i, j : double);
var
  tmp  : double;
begin
  tmp := i; i := j; j := tmp;
end;
  {*************************}
procedure read_f;
var
  i  : Integer;
  x1, x2, y1, y2 : double;
begin
  readln( n);
  for i := 1 to n do
    with R[i] do
      begin
        Id[i] := i;
        readln( x1, y1, x2, y2);
        if x1 > x2 then swap(x1, x2);
        if y1 > y2 then swap(y1, y2);
      end;
  readln( x0, y0);
end;
  {*************************}
function long(x1, y1, x2, y2 : double) : double;
begin
  long := Sqrt(sqr(x1 - x2) + sqr(y1 - y2));
end;
  {*************************}
function inside(i : Integer) : Boolean;
begin
  with R[i] do
    inside := (x0 >= x1) and (x0 <= x2) and (y0 >= y1) and (y0 <= y2);
end;
  {*************************}
function path(i : Integer) : double;
var
  tmp : double;
begin
  if inside(i) then
    begin
      path := 0;
      exit;
    end;
  with R[i] do
    begin
      tmp := 0;
      if (x1 <= x0) and (x0 <= x2) then
        begin
          tmp := maxLongInt;
          if tmp > abs(y0 - y1) then tmp := abs(y0 - y1);
          if tmp > abs(y0 - y2) then tmp := abs(y0 - y2);
          path := tmp; exit;
        end;
      if (y1 <= y0) and (y0 <= y2) then
        begin
          tmp := maxLongInt;
          if tmp > abs(x0 - x1) then tmp := abs(x0 - x1);
          if tmp > abs(x0 - x2) then tmp := abs(x0 - x2);
          path := tmp; exit;
        end;
      tmp := maxLongInt;
      if tmp > long(x1, y1, x0, y0) then tmp := long(x1, y1, x0, y0);
      if tmp > long(x1, y2, x0, y0) then tmp := long(x1, y2, x0, y0);
      if tmp > long(x2, y1, x0, y0) then tmp := long(x2, y1, x0, y0);
      if tmp > long(x2, y2, x0, y0) then tmp := long(x2, y2, x0, y0);
      path := tmp; exit;
    end;
end;
  {*************************}
procedure solve;
var
  i, j, tmp : Integer;
  t1 : double;
begin
  for i := 1 to n do
    for j := i + 1 to n do
      if Path(Id[i]) - Path(Id[j]) > (1e-14) then
        begin
          tmp := Id[i]; Id[i] := Id[j]; Id[j] := tmp;
        end;
end;
  {*************************}
procedure print;
var
  i : Integer;
begin
  for i := 1 to n do write( Id[i], ' ');
end;
  {*************************}
begin
  read_f;
  solve;
  print;
end.

var i,j,k,n,m:longint;
    a:array [1..100] of record x1,y1,x2,y2:integer; end;
    x,y:longint;
    r:array [0..100] of record r:real;i:integer; end;
function min(a,b:integer):integer; begin if a>b then min:=b else
min:=a; end;
function minr(a,b:real):real;      begin if a>b then minr:=b else
minr:=a;end;
function max(a,b:integer):integer; begin if a<b then max:=b else
max:=a; end;
function rr(x,y,x1,y1:Longint):real;begin rr:=sqrt(sqr(x-x1)+sqr(y-
y1)); end;
function inn(x1,x,x2:integer):boolean;
begin
if (min(x1,x2)<=x) and (x<=max(x1,x2)) then inn:=true else inn:=false;
end;

function r_kv_t(x1,y1,x2,y2:Longint):real;
var r1,r2,r3,r4:real;
begin
 if inn(x1,x,x2) and inn(y1,y,y2) then r_kv_t:=0 else
 begin
  if inn(x1,x,x2) then r_kv_t:=min(abs(y2-y),abs(y1-y));
  if inn(y1,y,y2) then r_kv_t:=min(abs(x2-x),abs(x1-x));
  r1:=rr(x1,y1,x,y);
  r2:=rr(x2,y2,x,y);
  r3:=rr(x1,y2,x,y);
  r4:=rr(x2,y1,x,y);
  r_kv_t:=minr(minr(r1,r2),minr(r3,r4));
 end;
end;

begin
 read(n);
 for i:=1 to n do read(a[i].x1,a[i].y1,a[i].x2,a[i].y2);
 read(x,y);
 for i:=1 to n do r[i].r:=r_kv_t(a[i].x1,a[i].y1,a[i].x2,a[i].y2);
 for i:=1 to n do r[i].i:=i;
 for i:=1 to n do
  for j:=i+1 to n do
  if r[i].r-r[j].r>1e-14 then
   begin
    r[0]:=r[i]; r[i]:=r[j]; r[j]:=r[0];
   end;
 for i:=1 to n-1 do write(r[i].i,' '); writeln(r[n].i);
end.

Why I get WA ??? I can not find the error any where

{$n+}
Program Square;

Type Lion=record
            x,y:double;
          end;
     xm=array[1..4] of Lion;

Var i,j,k,m,n,k1,k2:longint;
    V:xm;
    a:array[0..100] of xm;
    dis,x,y,sum,min:double;
    distance:array[0..100] of double;
    num:array[0..100] of integer;

Function Long(x,y,x1,y1:double):double;
begin
  Long:=sqrt(sqr(x1-x)+sqr(y1-y));
end;

Procedure Init;
Var Long1,arc,arc1:double;
Begin
  fillchar(v,sizeof(v),0);
  read(v[1].x,v[1].y,v[3].x,v[3].y);
  Long1:=Long(v[1].x,v[1].y,v[3].x,v[3].y)/sqrt(2);
  if v[1].x=v[3].x then
  begin
    v[2].x:=v[1].x-Long1/sqrt(2);
    v[2].y:=(v[1].y+v[3].y)/2;
    v[4].x:=v[1].x+Long1/sqrt(2);
    v[4].y:=(v[1].y+v[3].y)/2;
  end
  else
  begin
    arc:=arctan((v[3].y-v[1].y)/(v[3].x-v[1].x));
    if v[3].x-v[1].x<0 then arc:=arc+pi;
    arc1:=arc+pi/4;
    v[2].y:=v[1].y+Long1*sin(arc1);
    v[2].x:=v[1].x+Long1*cos(arc1);
    arc1:=arc-pi/4;
    v[4].y:=v[1].y+Long1*sin(arc1);
    v[4].x:=v[1].x+Long1*cos(arc1);
  end;

End;

Function Get(x1,y1,x2,y2:double):double;
var k,k1,b,b1,xx,yy,Long1,Long2:double;
begin
  if x1=x2 then
  begin
    xx:=x1;
    yy:=y;
  end
  else
  if y1<>y2 then
  begin
    k:=(y2-y1)/(x2-x1);
    b:=y1-k*x1;
    k1:=-1/k;
    b1:=y-k1*x;
    xx:=(b1-b)/(k-k1);
    yy:=xx*k1+b1;
  end
  else
  begin
    xx:=x;
    yy:=y1;
  end;
  if ((yy>=y1)and(yy<=y2)or(yy>=y2)and(yy<=y1))
  and((xx>=x1)and(xx<=x2)or(xx>=x2)and(xx<=x1)) then
  Get:=Long(xx,yy,x,y)
  else
  begin
    Long1:=Long(x1,y1,x,y);
    Long2:=Long(x2,y2,x,y);
    if Long1<Long2 then Get:=Long1
    else Get:=Long2;
  end;
  sum:=sum+Long(xx,yy,x,y);
end;

Begin
  read(n);
  fillchar(a,sizeof(a),0);
  fillchar(distance,sizeof(distance),0);
  for i:=1 to n do
  begin
    Init;
    a[i]:=v;
  end;
  read(x,y);
  for i:=1 to n do
  begin
    Min:=1e100;
    sum:=0;
    for j:=1 to 4 do
    begin
      k1:=j;
      if j=4 then k2:=1
      else k2:=j+1;
      dis:=get(a[i,k1].x,a[i,k1].y,a[i,k2].x,a[i,k2].y);
      if dis<min then
      Min:=dis;
    end;
    if abs(sum-Long(a[i,1].x,a[i,1].y,a[i,3].x,a[i,3].y)*sqrt(2))<1e-
14
    then distance[i]:=0
    else distance[i]:=Min;
  end;
  for i:=1 to n do num[i]:=i;
  for i:=1 to n-1 do
  for j:=i+1 to n do
  if distance[j]<distance[i] then
  begin
    k:=num[i];
    num[i]:=num[j];
    num[j]:=k;
    dis:=distance[i];
    distance[i]:=distance[j];
    distance[j]:=dis;
  end;
  for i:=1 to n do write(num[i],' ');
End.

var i,j,k,n,m:integer;
    x,y:integer;
    a:array [1..100,1..4] of integer;
    r:array [0..100] of real;
    b:array [0..100] of integer;


function minr(a,b : real):real;
begin
   if a<b then minr := a else minr := b;
end;

function min(a,b : integer):integer;
begin
   if a<b then min := a else min := b;
end;

function max(a,b : integer):integer;
begin
   if a>b then max := a else max := b;
end;

function len(x1,y1,x2,y2: real):real;
begin
   len := sqrt(sqr(x2-x1)+sqr(y2-y1));
end;

function ins(x1,x2,x : integer) : boolean;
begin
   if (x>=min(x1,x2)) and (x<=max(x1,x2)) then begin
      ins := true;
   end else ins := false;
end;

function sq_dis(x1,y1,x2,y2 : integer): real;
var d1,d2,d3,d4 : real;
begin
   if ins(x1,x2,x) and ins(y1,y2,y) then begin
      sq_dis := 0;
      exit;
   end;
   if ins(x1,x2,x) then
   begin
    d1:=abs(y1-y);
    d2:=abs(y2-y);
    d3:=abs(y1-y);
    d4:=abs(y2-y);
   end else begin
    if ins(y1,y2,y) then
    begin
     d1:=abs(x1-x);
     d2:=abs(x2-x);
     d3:=abs(x1-x);
     d4:=abs(x1-x);
    end else begin
     d1:=len(x1,y1,x,y);
     d2:=len(x2,y2,x,y);
     d3:=len(x2,y1,x,y);
     d4:=len(x1,y2,x,y);
    end;
   end;
  sq_dis := minr(minr(minr(d1,d2),d3),d4);
end;

function proov(k:integer):real;
var x1,x2,y1,y2:integer;
 function min(a,b:integer):integer;
 begin
  if a<b then min:=a else min:=b;
 end;

 function max(a,b:integer):integer;
 begin
  if a>b then max:=a else max:=b;
 end;
begin
 x1:=min(a[k,1],a[k,3]);
 y1:=max(a[k,2],a[k,4]);
 x2:=max(a[k,1],a[k,3]);
 y2:=min(a[k,2],a[k,4]);
 proov:=sq_dis(x1,y1,x2,y2);
end;

begin
 read(n);
 for i:=1 to n do
 begin
  for j:=1 to 4
  do read(a[i,j]);
  b[i]:=i;
 end;
 read(x,y);
 for i:=1 to n do r[i]:=proov(i);
 for i:=1 to n do
 begin
  for j:=i+1 to n do
  begin
   if r[i]>r[j] then
   begin
    r[0]:=r[i]; r[i]:=r[j]; r[j]:=r[0];
    b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
   end;
  end;
 end;
 for i:=1 to n do writeln(b[i],' ',r[i]:0:0)
end.

var i,j,k,n,m:integer;
    x,y:integer;
    a:array [1..100,1..4] of integer;
    r:array [0..100] of real;
    b:array [0..100] of integer;


function minr(a,b : real):real;
begin
   if a<b then minr := a else minr := b;
end;

function min(a,b : integer):integer;
begin
   if a<b then min := a else min := b;
end;

function max(a,b : integer):integer;
begin
   if a>b then max := a else max := b;
end;

function len(x1,y1,x2,y2: real):real;
begin
   len := sqrt(sqr(x2-x1)+sqr(y2-y1));
end;

function ins(x1,x2,x : integer) : boolean;
begin
   if (x>=min(x1,x2)) and (x<=max(x1,x2)) then begin
      ins := true;
   end else ins := false;
end;

function sq_dis(x1,y1,x2,y2,x3,y3,x4,y4 : integer): real;
var d1,d2,d3,d4 : real;
begin
   if ins(x1,x2,x) and ins(y1,y2,y) then begin
      sq_dis := 0;
      exit;
   end;
   if ins(x1,x2,x) then begin
      d1 := abs(y1-y);
   end else begin
      d1 := minr(len(x,y,x1,y1),len(x,y,x2,y2));
   end;
   if ins(x3,x4,x) then begin
      d2 := abs(y3-y);
   end else begin
      d2 := minr(len(x,y,x3,y3),len(x,y,x4,y4));
   end;
   if ins(y1,y4,y) then begin
      d3 := abs(x4-x);
   end else begin
      d3 := minr(len(x,y,x1,y1),len(x,y,x4,y4));
   end;
   if ins(y2,y3,y) then begin
      d4 := abs(x3-x);
   end else begin
      d4 := minr(len(x,y,x2,y2),len(x,y,x3,y3));
   end;
   sq_dis := minr(minr(minr(d1,d2),d3),d4);
end;

function proov(k:integer):real;
var x1,x2,y1,y2:integer;
 function min(a,b:integer):integer;
 begin
  if a<b then min:=a else min:=b;
 end;

 function max(a,b:integer):integer;
 begin
  if a>b then max:=a else max:=b;
 end;
begin
 x1:=min(a[k,1],a[k,3]);
 y1:=max(a[k,2],a[k,4]);
 x2:=max(a[k,1],a[k,3]);
 y2:=min(a[k,2],a[k,4]);
 proov:=sq_dis(x1,y1,x2,y1,x2,y2,x1,y2);
end;

begin
 read(n);
 for i:=1 to n do
 begin
  for j:=1 to 4
  do read(a[i,j]);
  b[i]:=i;
 end;
 read(x,y);
 for i:=1 to n do r[i]:=proov(i);
 for i:=1 to n do
 begin
  for j:=i+1 to n do
  begin
   if r[i]>r[j] then
   begin
    r[0]:=r[i]; r[i]:=r[j]; r[j]:=r[0];
    b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
   end;
  end;
 end;
 for i:=1 to n do writeln(b[i],' ',r[i]:0:0)
end.

{$N+}
const
maxn = 100;
zero = 1e-14;
type
tpoint = record
x, y: double;
end;
tsquare = record
p1, p2, p3, p4: tpoint;
end;
var
dis: array[1..maxn]of double;
sq: array[1..maxn]of tsquare;
num: array[1..maxn]of integer;
n, i, j, t0: integer;
p0: tpoint;
t: double;
function min(a, b, c, d: double): double;
var
res: double;
begin
res := a;
if b < res then res := b;
if c < res then res := c;
if d < res then res := d;
min := res;
end;

function distant(p1, p2: tpoint): double;
var
res: double;
begin
res := sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
distant := res;
end;

function d(pn, pm: tpoint): double;
var
res, p, a, b, c: double;
begin
a := distant(pn, p0);
b := distant(pm, p0);
c := distant(pn, pm);
if (a + b = c)or(a - b = c)or(b - a = c) then
begin
d := 0;
exit;
end;
if (a = 0)or(b = 0) then
begin
d := 0;
exit;
end;
if( (sqr(c) + sqr(b) - sqr(a))/(b * c) < 0 )
or( (sqr(c) + sqr(a) - sqr(b))/(a * c) < 0 ) then
res := min(a, b, maxlongint, maxlongint)
else
begin
p := (a + b + c) / 2;
res := 2 * sqrt(p * (p - a) * (p - b) * (p - c)) / c;
end;
d := res;

end;

begin
readln(n);
fillchar(sq, sizeof(sq), 0);
fillchar(dis, sizeof(dis), 0);
for i := 1 to n do
with sq[i] do
begin
readln(p1.x, p1.y, p3.x, p3.y);
p2.x := (p1.x + p3.x) / 2 - (p3.y - p1.y) / 2;
p2.y := p3.y - (p1.x - p2.x);
p4.x := (p1.x + p3.x) / 2 + (p3.y - p1.y) / 2;
p4.y := p1.y + (p4.x - p3.x);
end;
readln(p0.x, p0.y);
for i := 1 to n do
with sq[i] do
begin
dis[i] := min(d(p1, p2), d(p2, p3), d(p3, p4), d(p4, p1));
if abs(d(p2, p3) + d(p4, p1) - distant(p1, p2)) <= 1e-10 then
dis[i] := 0;
end;
for i := 1 to n do
num[i] := i;
for i := 1 to n - 1 do
for j := i + 1 to n do
if dis[i] > dis[j] then
begin
t := dis[i]; dis[i] := dis[j]; dis[j] := t;
t0 := num[i]; num[i] := num[j]; num[j] := t0;
end
else if abs(dis[i] - dis[j]) <= zero then
if num[i] > num[j] then
begin
t0 := num[i]; num[i] := num[j]; num[j] := t0;
end;
for i := 1 to n do write(num[i], ' ');
end.

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 65520,0,655360}
type uu=record
         x,y:extended;
        end;
var mindis:array[1..100] of extended;
    num:array[1..100] of integer;
    zuob:array[1..100,1..2,1..2] of uu;

a1,a2,b1,b2,c1,c11,c2,l1,l2,xx,yy,xp,yp,xj,yj,min,bc,mm,t:extended;
    n,i,j,k,bb,tt,a,b,c,d:integer;

procedure xyz(a1,b1,c1,a2,b2,c2:extended;var x,y:extended);
begin
 x:=(b1*c2-b2*c1)/(a1*b2-a2*b1);
 y:=(c1*a2-c2*a1)/(a1*b2-a2*b1);
end;

function distan(x1,y1,x2,y2:extended):extended;
begin
 distan:=sqrt(abs(sqr(x1-x2))+abs(sqr(y1-y2)));
end;

begin
 readln(n);
 for i:=1 to n do
 begin
  num[i]:=i;
  for j:=1 to 2 do read(zuob[i,1,j].x,zuob[i,1,j].y);
  a1:=zuob[i,1,1].y-zuob[i,1,2].y;
  b1:=zuob[i,1,2].x-zuob[i,1,1].x;
  c1:=(zuob[i,1,2].y-zuob[i,1,1].y)*zuob[i,1,2].x+(zuob[i,1,1].x-zuob
[i,1,2].x)*zuob[i,1,2].y;
  c11:=c1;
  l1:=distan(zuob[i,1,1].x,zuob[i,1,1].y,zuob[i,1,2].x,zuob
[i,1,2].y)/2;
  xx:=(zuob[i,1,1].x+zuob[i,1,2].x)/2;
  yy:=(zuob[i,1,1].y+zuob[i,1,2].y)/2;
  a2:=-b1;
  b2:=a1;
  c2:=-(a2*xx+b2*yy);
  c1:=c11-sqrt(a1*a1+b1*b1)*l1;
  xyz(a1,b1,c1,a2,b2,c2,zuob[i,2,1].x,zuob[i,2,1].y);
  c1:=c11+sqrt(a1*a1+b1*b1)*l1;
  xyz(a1,b1,c1,a2,b2,c2,zuob[i,2,2].x,zuob[i,2,2].y);
 end;
 readln(xp,yp);
 for i:=1 to n do
 begin
  bb:=0;
  mm:=1e+10;
  bc:=distan(zuob[i,1,1].x,zuob[i,1,1].y,zuob[i,1,2].x,zuob
[i,1,2].y)/2*sqrt(2);
  for a:=1 to 2 do
   for b:=1 to 2 do
    for c:=1 to 2 do
    if a<>c then
    for d:=1 to 2 do
    if (zuob[i,a,b].y<>zuob[i,c,d].y)or(zuob[i,c,d].x<>zuob[i,a,b].x)
then
    begin
     a1:=zuob[i,a,b].y-zuob[i,c,d].y;
     b1:=zuob[i,c,d].x-zuob[i,a,b].x;
     c1:=(zuob[i,c,d].y-zuob[i,a,b].y)*zuob[i,c,d].x+(zuob[i,a,b].x-
zuob[i,c,d].x)*zuob[i,c,d].y;
     a2:=-b1;
     b2:=a1;
     c2:=-(a2*xp+b2*yp);
 {    xj:=(b1*c2-b2*c1)/(a1*b2-a2*b1);
     yj:=(c1*a2-c2*a1)/(a1*b2-a2*b1);}
     if ((zuob[i,a,b].x-xj)*(zuob[i,c,d].x-xj)<=0)and
     ((zuob[i,a,b].y-yj)*(zuob[i,c,d].y-yj)<=0) then
     min:=distan(xp,yp,xj,yj) else
     begin
      l1:=distan(xp,yp,zuob[i,a,b].x,zuob[i,a,b].y);
      if l1<1e-14 then l1:=0;
      l2:=distan(xp,yp,zuob[i,c,d].x,zuob[i,c,d].y);
      if l1<l2 then min:=l1
               else min:=l2;
     end;
     if min>bc then bb:=1;
     if min<mm then mm:=min;
    end;
  if bb=0 then mm:=0;
  mindis[i]:=mm;
 end;
 for i:=1 to n-1 do
 begin
  k:=i;
  for j:=i+1 to n do
  if mindis[j]<mindis[k] then k:=j;
  if i<>k then
  begin
   t:=mindis[i];
   mindis[i]:=mindis[k];
   mindis[k]:=t;
   tt:=num[i];
   num[i]:=num[k];
   num[k]:=tt;
  end;
 end;
 for i:=1 to n do
 write(num[i],' ');
end.

var
  c:array[0..100]of double;
  a:array[0..100]of byte;
  p:array[1..100,1..14]of double;
  n,i,j:byte;
  d,b,mx,my,p1,p2,p3,p4,p5,p6,p7,p8,r1,r2,c1,c2,c3,c4:double;
begin
  read(n);
  for i:=1to n do
  begin
    read(p1,p2,p3,p4);a[i]:=i;
    d:=sqrt(sqr(p1-p3)+sqr(p2-p4));
    mx:=(p1+p3)/2;my:=(p2+p4)/2;
    p5:=mx+p2-my;p6:=my+mx-p1;
    p7:=mx-p2+my;p8:=my-mx+p1;
    if p1=p5 then r1:=1e2466else r1:=(p2-p6)/(p1-p5);if r1=0then
r2:=1e2466else r2:=-1/r1;
    c1:=p1*r1-p2;c2:=p7*r1-p8;c3:=p5*r2-p6;c4:=p7*r2-p8;
    p[i,1]:=p1;p[i,2]:=p2;p[i,3]:=p3;p[i,4]:=p4;p[i,5]:=p5;p
[i,6]:=p6;p[i,7]:=p7;p[i,8]:=p8;
    p[i,9]:=r1;p[i,10]:=r2;p[i,11]:=c1;p[i,12]:=c2;p[i,13]:=c3;p
[i,14]:=c4
  end;
  read(p1,p2);
  for i:=1to n do
  if abs(p[i,1]-p[i,3])=abs(p[i,2]-p[i,4])then
  begin
    if((p1>=p[i,1])and(p1<=p[i,3])or(p1<=p[i,1])and(p1>=p[i,3]))and
    ((p2>=p[i,2])and(p2<=p[i,4])or(p2<=p[i,2])and(p2>=p[i,4]))then c
[i]:=0
    else if(p1>=p[i,1])and(p1<=p[i,3])or(p1<=p[i,1])and(p1>=p[i,3])
then
    if abs(p2-p[i,2])<abs(p2-p[i,4])then c[i]:=abs(p2-p[i,2])else c
[i]:=abs(p2-p[i,4])
    else if(p2>=p[i,2])and(p2<=p[i,4])or(p2<=p[i,2])and(p2>=p[i,4])
then
    if abs(p1-p[i,1])<abs(p1-p[i,3])then c[i]:=abs(p1-p[i,1])else c
[i]:=abs(p1-p[i,3])
    else begin
      c1:=sqrt(sqr(p1-p[i,1])+sqr(p2-p[i,2]));
      c2:=sqrt(sqr(p1-p[i,3])+sqr(p2-p[i,4]));
      c3:=sqrt(sqr(p1-p[i,5])+sqr(p2-p[i,6]));
      c4:=sqrt(sqr(p1-p[i,7])+sqr(p2-p[i,8]));
      if(c1<=c2)and(c1<=c3)and(c1<=c4)then c[i]:=c1 else
      if(c2<=c1)and(c2<=c3)and(c2<=c4)then c[i]:=c2 else
      if(c3<=c1)and(c3<=c2)and(c3<=c4)then c[i]:=c3 else
      if(c4<=c1)and(c4<=c2)and(c4<=c3)then c[i]:=c4
    end
  end else
  begin
    if((p[i,9]*p1-p2>p[i,11])and(p[i,9]*p1-p2>p[i,12])or(p[i,9]*p1-
p2<p[i,11])and(p[i,9]*p1-p2<p[i,12]))and
    ((p[i,10]*p1-p2>p[i,13])and(p[i,10]*p1-p2>p[i,14])or(p[i,10]*p1-
p2<p[i,13])and(p[i,10]*p1-p2<p[i,14]))then
    begin
      c1:=sqrt(sqr(p1-p[i,1])+sqr(p2-p[i,2]));
      c2:=sqrt(sqr(p1-p[i,3])+sqr(p2-p[i,4]));
      c3:=sqrt(sqr(p1-p[i,5])+sqr(p2-p[i,6]));
      c4:=sqrt(sqr(p1-p[i,7])+sqr(p2-p[i,8]));
      if(c1<=c2)and(c1<=c3)and(c1<=c4)then c[i]:=c1 else
      if(c2<=c1)and(c2<=c3)and(c2<=c4)then c[i]:=c2 else
      if(c3<=c1)and(c3<=c2)and(c3<=c4)then c[i]:=c3 else
      if(c4<=c1)and(c4<=c2)and(c4<=c3)then c[i]:=c4
    end else if((p[i,9]*p1-p2>=p[i,11])and(p[i,9]*p1-p2<=p[i,12])or(p
[i,9]*p1-p2<=p[i,11])and(p[i,9]*p1-p2>=p[i,12]))and
    ((p[i,10]*p1-p2<=p[i,13])and(p[i,10]*p1-p2>=p[i,14])or(p[i,10]*p1-
p2>=p[i,13])and(p[i,10]*p1-p2<=p[i,14]))then c[i]:=0 else
    if(p[i,9]*p1-p2>p[i,11])and(p[i,9]*p1-p2<p[i,12])or(p[i,9]*p1-p2<p
[i,11])and(p[i,9]*p1-p2>p[i,12])then
    begin
      c1:=abs(p[i,10]*p1-p2-p[i,14])/sqrt(sqr(p[i,10])+1);
      c2:=abs(p[i,10]*p1-p2-p[i,13])/sqrt(sqr(p[i,10])+1);
      if c1<c2 then c[i]:=c1 else c[i]:=c2
    end else
    begin
      c1:=abs(p[i,9]*p1-p2-p[i,12])/sqrt(sqr(p[i,9])+1);
      c2:=abs(p[i,9]*p1-p2-p[i,11])/sqrt(sqr(p[i,9])+1);
      if c1<c2 then c[i]:=c1 else c[i]:=c2
    end
  end;
  for i:=1to n-1do
  for j:=i+1to n do
  if(c[i]>c[j])or(c[i]=c[j])and(a[i]>a[j])then
  begin
    c[0]:=c[i];c[i]:=c[j];c[j]:=c[0];
    a[0]:=a[i];a[i]:=a[j];a[j]:=a[0]
  end;
  for i:=1to n do
  write(a[i],' ')
end.

{Written by Luguev Timur}
{$n+}
uses crt;
const max=32767;
var
  input,out:text;
  n,i,j:byte;
  c:array[1..100,1..4] of integer;
  res:array[1..100] of extended;
  xp,yp:integer;

procedure load;
begin
  readln(input,n);
  for i:=1 to n do
  begin
    read(input,c[i,1]);
    read(input,c[i,2]);
    read(input,c[i,3]);
    readln(input,c[i,4]);
  end;
  read(input,xp);
  read(input,yp);
end;

function dbetp(x1,y1,x2,y2:extended):extended;
begin
  dbetp:=sqrt(sqr(x2-x1)+sqr(y2-y1));
end;
{-------------------------------------------------------}
function finddistance(x1,y1,x3,y3:integer):extended;
var
  x2,y2,x4,y4,x,y:extended;
  k12,k23,k34,k41,k,c12,c23,c34,c41:extended;
  d:extended;
procedure findcoord(k,c,x1,y1:extended;var x,y:extended);
var c1:extended;
begin
  c1:=y1+x1/k;
  x:=(k*(c1-c))/(sqr(k)-1);
  y:=(sqr(k)*(c1-c))/(sqr(k)-1)+c;
end;

procedure findk;
begin
  k:=(y3-y1)/(x3-x1);
  k12:=(1+k)/(1-k);
  k34:=k12;
  k23:=(k-1)/(1+k);
  k41:=k23;
  c12:=y1-k12*x1;
  c23:=y3-k23*x3;
  c34:=y3-k34*x3;
  c41:=y1-k41*x1;
end;

procedure findxy;
begin
  if x1=x3 then
  begin
    if y3>y1 then
    begin
      x2:=x1-abs(x2-x3);
      x4:=x1+abs(x2-x3);
      y2:=(y3-y1)/2;
      y4:=y2;
    end
    else
    begin
      x2:=x1+abs(x2-x3);
      x4:=x1-abs(x2-x3);
      y2:=(y1-y3)/2;
      y4:=y2;
    end;
    exit;
  end;
  if y1=y3 then
  begin
    if x3>x1 then
    begin
      x2:=(x1+x3)/2;
      x4:=x2;
      y2:=(x3-x1)/2+y1;
      y4:=y1-(x3-x1)/2;
    end
    else
    begin
      x2:=(x1+x3)/2;
      x4:=x2;
      y4:=(x1-x3)/2+y1;
      y2:=y1-(x1-x3)/2;
    end;
    exit;
  end;
  findk;
  findcoord(k23,c23,x1,y1,x2,y2);
  findcoord(k34,c34,x1,y1,x4,y4);
end;
procedure exception;
var
  a,b,c,l:extended;
begin
  if (x3>x1) and (y3<y1) then
  begin
    a:=x1;
    c:=x3;
    b:=y1;
    l:=y3;
  end;
  if (x3<x1) and (y3>y1) then
  begin
    a:=x3;
    c:=x1;
    b:=y3;
    l:=y1;
  end;
  if (x3>x1) and (y3>y1) then
  begin
    a:=x1;
    b:=y3;
    c:=x3;
    l:=y1;
  end;
  if (x3<x1) and (y3<y1) then
  begin
    a:=x3;
    b:=y1;
    c:=x1;
    l:=y3
  end;
  if (xp>=a) and (xp<=c) and (yp<=b) and (yp>=l) then
  begin
    d:=0;
    exit;
  end;
  if (xp<a) and (yp>b) then d:=dbetp(xp,yp,a,b);
  if (xp>=a) and (xp<=c) and (yp>b) then d:=yp-b;
  if (xp>c) and (yp>b) then d:=dbetp(xp,yp,c,b);
  if (xp<a) and (yp<=b) and (yp>=l) then d:=a-xp;
  if (xp>c) and (yp<=b) and (yp>=l) then d:=xp-c;
  if (xp<a) and (yp<l) then d:=dbetp(xp,yp,a,l);
  if (xp>=a) and (xp<=c) and (yp<l) then d:=l-yp;
  if (xp>c) and (yp<l) then d:=dbetp(xp,yp,c,l);
end;
function test:boolean;
var
  x12,y12,x23,y23,x34,y34,x41,y41:extended;
begin
  test:=false;
  findcoord(k12,c12,xp,yp,x12,y12);
  findcoord(k23,c23,xp,yp,x23,y23);
  findcoord(k34,c34,xp,yp,x34,y34);
  findcoord(k12,c12,xp,yp,x41,y41);
  if ((dbetp(x12,y12,xp,yp)+dbetp(x34,y34,xp,yp))=dbetp
(x12,y12,x34,y34)) and
  ((dbetp(x23,y23,xp,yp)+dbetp(x41,y41,xp,yp))=dbetp
(x23,y23,x41,y41)) then
  test:=true;
end;
begin
  if (x3=x1) and (y1=y3) then
  begin
    finddistance:=dbetp(x1,y1,xp,yp);
    exit;
  end;
  if (abs(x3-x1)=abs(y3-y1)) then
  begin
    exception;
    finddistance:=d;
    exit;
  end;
  findxy;
  if test then
  begin
    finddistance:=0;
    exit;
  end;
  d:=max;
  if dbetp(x1,y1,xp,yp)<d then d:=dbetp(x1,y1,xp,yp);
  if dbetp(x2,y2,xp,yp)<d then d:=dbetp(x2,y2,xp,yp);
  if dbetp(x3,y3,xp,yp)<d then d:=dbetp(x3,y3,xp,yp);
  if dbetp(x4,y4,xp,yp)<d then d:=dbetp(x4,y4,xp,yp);
  findcoord(k12,c12,xp,yp,x,y);
  if ((dbetp(x,y,x1,y1