To calculate the distance, rotate the square and the point so that the diagonal (if it is not a zero vector) becomes parallel to (1,1). In this case sides of the square are parallel to axes and the distance is trivial to calculate.

The problem can be solved without floating point operations: the square of the distance is a rational number. But note that to compare (an/ad < bn/bd) you cannot use (an*bd < bn*ad) since the products can overflow 64-bit integers. Instead first compare the integer parts, and in case they are equal to the same number, subtract this number from both parts and compare the results using multiplication (denominators are 32-bit integers).

can anyone send me right algorith to this problem with AC code? I tried many times to solve but i couldn't. my e-mail is shohruhhon1@mail.ru

why i'm getting WA2?

here is my code

program acm_1111_1;

label W;

const Eps=1e-15;

type
 Square=record
 X1,Y1,X3,Y3:real;
 X2,Y2,X4,Y4:real;
end;

type
 Point=record
 X,Y:real;
end;

var p:array[1..100] of Square;
    Dis:array[1..100] of real;
    ID:array[1..100] of integer;
    Q,O:Point;
    r,sd1,sd2,sd3,sd4,vd1,vd2,vd3,vd4:real;
    Dist:real;
    i,j,kk,n:integer;

function L1_2(i:integer; A:Point; B:Point):real;
var a1,b1:real;
begin
 a1:=p[i].X2-p[i].X1;  b1:=p[i].Y2-p[i].Y1;
 L1_2:=a1*(B.X-A.X)-b1*(B.Y-A.Y);
end;

function L1_4(i:integer; A:Point; B:Point):real;
var a1,b1:real;
begin
 a1:=p[i].X4-p[i].X1;  b1:=p[i].Y4-p[i].Y1;
 L1_4:=a1*(B.X-A.X)-b1*(B.Y-A.Y);
end;

function min(aa,bb,cc,dd:real):real;
var mn:real;
begin
 mn:=aa;
 if bb<mn then mn:=aa;
 if cc<mn then mn:=cc;
 if dd<mn then mn:=dd;
 min:=mn;
end;

begin
  read(n);
  for i:=1 to n do
  begin
   read(p[i].X1,p[i].Y1,p[i].X3,p[i].Y3);
   O.X:=(p[i].X1+p[i].X3)/2; O.Y:=(p[i].Y1+p[i].Y3)/2;
   r:=sqrt(sqr(p[i].X1-p[i].X3)+sqr(p[i].Y1-p[i].Y3))/2;
   p[i].X2:=-(p[i].Y1-p[i].Y3)/2+O.X;
   p[i].Y2:=(p[i].X1-p[i].X3)/2+O.Y;
   p[i].X4:=(p[i].Y1-p[i].Y3)/2+O.X;
   p[i].Y4:=-(p[i].X1-p[i].X3)/2+O.Y;
  end;
  read(Q.X,Q.Y);

  for i:=1 to n do
  begin
   r:=sqrt(sqr(p[i].X1-p[i].X2)+sqr(p[i].Y1-p[i].Y2));

   vd1:=sqrt(sqr(Q.X-p[i].X1)+sqr(Q.Y-p[i].Y1));
   vd2:=sqrt(sqr(Q.X-p[i].X2)+sqr(Q.Y-p[i].Y2));
   vd3:=sqrt(sqr(Q.X-p[i].X3)+sqr(Q.Y-p[i].Y3));
   vd4:=sqrt(sqr(Q.X-p[i].X4)+sqr(Q.Y-p[i].Y4));

   O.X:=p[i].X1;  O.Y:=p[i].Y1;
   sd1:=abs(L1_4(i,Q,O))/r;   sd2:=abs(L1_2(i,Q,O))/r;
   O.X:=p[i].X3;  O.Y:=p[i].Y3;
   sd3:=abs(L1_4(i,O,Q))/r;  sd4:=abs(L1_2(i,O,Q))/r;

   if (abs(sd1)<Eps) or (abs(sd2)<Eps) or (abs(sd3)<Eps) or (abs(sd4)<Eps) then
   begin
    Dist:=min(vd1,vd2,vd3,vd4);
    goto W;
   end;

   if abs(sd1+sd3-r)<Eps then
   begin
    if abs(sd2+sd4-r)<Eps then begin Dist:=0; end;
    if abs(sd2-sd4-r)<Eps then begin Dist:=sd4; end;
    if abs(-sd2+sd4-r)<Eps then begin Dist:=sd2; end;
   end;

   if abs(sd1-sd3-r)<Eps then
   begin
    if abs(sd2+sd4-r)<Eps then begin Dist:=sd3; end;
    if abs(sd2-sd4-r)<Eps then begin Dist:=sd2; end;
    if abs(-sd2+sd4-r)<Eps then begin Dist:=vd2; end;
   end;

   if abs(-sd1+sd3-r)<Eps then
   begin
    if abs(sd2+sd4-r)<Eps then begin Dist:=sd1; end;
    if abs(sd2-sd4-r)<Eps then begin Dist:=vd4; end;
    if abs(-sd2+sd4-r)<Eps then begin Dist:=vd1; end;
   end;

W: Dis[i]:=abs(Dist);
   ID[i]:=i;
  end;

  for i:=1 to n-1 do
  for j:=i+1 to n do
  begin
   if Eps<Dis[i]-Dis[j] then
   begin
    Dist:=Dis[i];  Dis[i]:=Dis[j];  Dis[j]:=Dist;
    kk:=ID[i]; ID[i]:=ID[j];  ID[j]:=kk;
   end;
   if abs(Dis[i]-Dis[j])<=Eps then
   if ID[i]>ID[j] then
   begin
    kk:=ID[i]; ID[i]:=ID[j];  ID[j]:=kk;
   end;
  end;

  for i:=1 to n do write(ID[i],' '); writeln;
end.

I'm not seeing any disadvantages.....
Can you help me.

Thanks in advance

I got WA#3,after a day I suddenly found that my simple sort is not stable!!So MIND YOUR SORT!!

Is test 10 correct? A couple old AC solutions now have WA 10, and my new solution too.



Edited by author 29.04.2009 21:16

if you get WA1 or WA2 try to test:

3
0 0 1 1
0 3 1 4
4 2 4 4
3 1

right answer = 3 1 2
._
|_|
.
...../\
.....\/
._
|_|
.

This is square but not rectangle! ;)
I used simple geometric from

http://hardfire.jino-net.ru/index.php?id=77&cp=40563b52a55df6f5dfc9732f78ae175b

Good luks! :)

Edited by author 29.06.2008 14:30

To those who WA 8:
Try to change your epsilon to something else then 1e-14.
I changed that to 1e-8 and then I got AC.

Also, don't calculate S△ABC as 0.5*AB*AC! It should be 0.5*AB*AC*sin∠A

Check is your sorting is stable

Could anybody help me?? If u need i can post my code.

Qalaysan

Please, post some tests...

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!!!

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

{$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...

// 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

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;
}

{}{$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.