A could do the simple solution there I have 4 points of square and simple calculations of dist to this square. But i found this very easy and i figure out difficult formula for equations of the lines which bounding this square. I calculates dist for this lines and analyzing them.

This is initialization of square:
/*
void init(Point p1, Point p2){
    int64_t dx = p1.x-p2.x, dy = p1.y-p2.y;
    a = dx + dy; // some coof for line-equation
    b = dx - dy;
    c1 = dx*(p1.x-p1.y) + dy*(p1.x+p1.y);
    c2 = dy*(p2.x-p2.y) - dx*(p2.x+p2.y);
    dc = dx*dx + dy*dy; // delta between c-coof two parallel lines
    if (dc == 0) {
        // if square is dot
        c1 = p1.x;
        c2 = p1.y;
   }
}
*/
There i calculate dists to lines
/*
if (dc == 0){
    return std::hypot((p0.x - c1), (p0.y - c2));
} else {
    double
    d1 = (b*(p0.y) - a*(p0.x) + c1)/sqrt(2*dc), // signed dist to first line
    d2 = (b*(p0.x) + a*(p0.y) + c2)/sqrt(2*dc), // signed dist to perpendicular to first line
    d = sqrt(dc/2.0); // delta between two parallel lines (a side of square)
......
*/
"d" always is positive (if square isn't dot), bcs "(d1 - d) < d1" (dist to nearest line less than dist to farthest line)



there is some conditionals for calculate the dist to square
/*
if (d1 < 0) {
    if (d2 < 0) {
        // 1 corner   x1 = (c1*a - c2*b)/(2.0*dc), y1 = (-c1*b - c2*a)/(2.0*dc)
    } else if(d2 <= d){
        // 1 side
        return fabs(d1);
    } else {
        // 2 corner   x2 = (c1*a - c2*b)/(2.0*dc) + (b/2.0), y2 = (-c1*b - c2*a)/(2.0*dc) + (a/2.0)
    }
} else if (d1 <= d) {
    if (d2 < 0){
        // 2 side
        return fabs(d2);
    } else if(d2 <= d){
        // inside square
        return 0;
    } else {
        // 3 side
        return fabs(d2 - d);
    }
} else {
    if (d2 < 0){
        // 3 corner   x3 = (c1*a - c2*b)/(2.0*dc) - (a/2.0), y3 = (-c1*b - c2*a)/(2.0*dc) + (b/2.0)
    } else if(d2 <= d){
        // 4 side
        return fabs(d1 - d);
    } else {
        // 4 corner   x4 = (c1*a-c2*b)/(2.0*dc) + (b-a)/2.0, y4 = (p0.y + (c1*b+c2*a)/(2.0*dc) + (a+b)/2.0
    }
}
*/
after this we sorting dist with num, and print the answer

tests:
8
0 0 2 2
2 4 0 6
-8 -3 -8 -7
7 11 4 15
5 -5 9 -6
-2 -2 -2 -4
-4 6 -8 10
6 6 10 6
.....
6 2 : ans is "8 1 2 5 6 4 7 3"
0 0 : ans is "1 6 2 5 7 3 8 4"

Edited by author 26.08.2020 02:41

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

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N,a[55],b[55],i,c[55],j,d[55],e[55],m,n;
    unsigned long long x,y,arr[55];
    cin>>N;
    for(i=0;i<N;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        e[i]=i;
    }
    cin>>m>>n;
    for(i=0;i<N;i++){
        x=max(a[i]-m,m-c[i]);
        if(x<0){
            x=0;
        }
        y=max(b[i]-n,n-d[i]);
        if(y<0){
            y=0;
        }
        arr[i]=x*x+y*y;
    }
    for(i=0;i<N;i++){
        for(j=i+1;j<N;j++){
            if(arr[i]>a[j]){
                arr[i]=arr[j];
                e[i]=e[j];
            }
        }
    }
        for(i=0;i<N;i++){
            cout<<e[i]+1<<endl;
        }

    return 0;
}

The problem is rather easy, just compare squares due to rationality of numbers

Could you specify in the problem statement that the coordinates of the point in the last line are integer?

Also, could you specify the kind of precision near 10^{-14}? Is it absolute or relative?

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

When you compare in the sort, try using epsilon = 1e-8.

When I used 1e-13, I keep getting WA#3.

I have found two other points of square by this formula
 xc = (x1 + x3) / 2.0;
 yc = (y1 + y3) / 2.0;
 dx = (x3 - x1) / 2.0;
 dy = (y3 - y1) / 2.0;
 x2 = xc - dy;
 y2 = yc + dx;
 x4 = xc + dy;
 y4 = yc - dx;
But i could not understood why this works.

Then I use vector product to determine position of point etc.

Can someone explain me ?

5
0 1 0 1
0 1 0 1
0 1 0 1
-9999 -9999 9999 -9999
-9999 9999 9999 9999
0 0

answer is 4 5 1 2 3


5
0 1 0 1
0 1 0 1
0 1 0 1
-9999 9999 9999 9999
-9999 -9999 9999 -9999
0 0

answer is 4 5 1 2 3

Good luck!

It's my program:

{$N+}
Program p1111;

Type
  TPoint=Record
           x,y:Double;
         End;

Var
  Point:Array[1..100,1..2] Of TPoint;
  Len:Array[1..100] Of Double;
  num:Array[1..100] Of Integer;
  n:Integer;
  po:TPoint;

  Procedure Other(p1,p2:TPoint;Var p3,p4:TPoint);
  Var m,n:Double;
      po:TPoint;
  Begin
    po.x:=(p1.x+p2.x)/2;
    po.y:=(p1.y+p2.y)/2;
    n:=p1.x-po.x;m:=p1.y-po.y;
    p3.x:=m;p3.y:=-n;
    p4.x:=-p3.x;p4.y:=n;
    p3.x:=p3.x+po.x;p3.y:=p3.y+po.y;
    p4.x:=p4.x+po.x;p4.y:=p4.y+po.y;
  End;

  Procedure Init;
  Var
    i:Integer;
  Begin
    {$IFNDEF ONLINE_JUDGE}
    Assign(Input,'1111.Txt');
    Reset(Input);
    {$ENDIF}
    Readln(n);
    For i:=1 To n Do
      Readln(Point[i,1].x,Point[i,1].y,
             Point[i,2].x,Point[i,2].y);
    Readln(po.x,po.y);
  End;

  Procedure Main;
  Var
    i,j,k:Integer;
    p:Array[1..5] Of TPoint;
    u,A,B,C,L1,L2,L3,q1,q2,S:Double;
  Begin
    For i:=1 To n Do
    Begin
      num[i]:=i;
      p[1]:=Point[i,1];
      p[3]:=Point[i,2];
      Other(p[1],p[3],p[2],p[4]);
      p[5]:=p[1];
      L1:=sqr(p[1].x-p[2].x)+sqr(p[1].y-p[2].y);
      If Abs(L1)<1e-14
      Then Begin
             Len[i]:=sqr(po.x-p[1].x)+sqr(po.y-p[1].y);
             Continue;
           End;
      S:=0;
      For j:=1 To 4 Do
      Begin
        q1:=sqrt(sqr(po.x-p[j].x)+sqr(po.y-p[j].y));
        q2:=sqrt(sqr(po.x-p[j+1].x)+sqr(po.y-p[j+1].y));
        u:=(q1+q2+sqrt(L1))/2;
        S:=S+sqrt(u*(u-q1)*(u-q2)*(u-sqrt(L1)));
      End;
      If Abs(S-L1)<1e-14
      Then Begin
             Len[i]:=0;
             Continue;
           End;
      S:=1e300;
      For j:=1 To 4 Do
      Begin
        A:=p[j+1].y-p[j].y;
        B:=p[j].x-p[j+1].x;
        C:=-A*p[j].x-B*p[j].y;
        L2:=sqr(p[j].x-po.x)+sqr(p[j].y-po.y);
        L3:=sqr(p[j+1].x-po.x)+sqr(p[j+1].y-po.y);
        If not((L1+L3-L2<0)or(L1+L2-L3<0))
        Then Begin
               u:=Sqr(A*po.x+B*po.y+C)/(A*A+B*B);
               If u<S
               Then S:=u;
             End;
      End;
      For j:=1 To 4 Do
      Begin
        u:=Sqr(po.x-p[j].x)+Sqr(po.y-p[j].y);
        If u<S
        Then S:=u;
      End;
      Len[i]:=S;
    End;
    For i:=1 To n-1 Do
      For j:=i+1 To n Do
      If Len[i]>Len[j]
      Then Begin
             S:=Len[i];
             Len[i]:=Len[j];
             Len[j]:=s;
             k:=num[i];
             num[i]:=num[j];
             num[j]:=k;
           End;
    For i:=1 To n-1 Do
      Write(num[i],' ');
    Writeln(num[n]);
  End;

Begin
  Init;
  Main;
End.

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).

what would be the distance between point (0,0) and square (1,0) (-1,0)?? Is it equal 0 or 0.7??

#include <stdio.h>
#include <math.h>
#define M_PI_4     0.785398163397448309616

double d[51] = {0};
char printed[51] = {0};

struct point {
double x;
double y;
};

struct square {
point a;
point b;
} squares[51];

point rotate(point a, double d_al){
point _a;
_a.x = a.x * cos(d_al) - a.y * sin(d_al);
_a.y = a.x * sin(d_al) + a.y * cos(d_al);
return _a;
}

double get_d(point a, point p) {
return sqrt((double)((a.x - p.x)*(a.x-p.x) + (a.y -p.y)*(a.y - p.y)));
}

int main () {
    int n;
    scanf("%d",&n);
    point p;
    int i;
    for (i=1;i<=n;i++) {
        scanf("%lf%lf%lf%lf", &squares[i].a.x,&squares[i].a.y,&squares[i].b.x,&squares[i].b.y);
    }
    scanf("%lf%lf", &p.x,&p.y);
    double tn;
    double alpha,d_al;
    point _a,_b,_p,a,b,temp;
    for(i=1;i<=n;i++) {
        b = squares[i].b;
        a = squares[i].a;
        if(a.x == b.x && a.y == b.y) {
            d[i] = get_d(p,a);
            continue;
        }
        tn = (double)(b.y - a.y)/(double)(b.x - a.x);
        alpha = atan(tn);
        d_al = M_PI_4 - alpha;
        _a = rotate(a,d_al);
        _b = rotate(b,d_al);
        _p = rotate(p,d_al);
        if( _a.x > _b.x) {
            temp = _b;
            _b = _a;
            _a = temp;
        }

        if(_p.y > _b.y) {
            if(_p.x < _a.x) {
                temp.x = _a.x;
                temp.y = _b.y;
                d[i] = get_d(_p,temp);
                continue;
            }
            if(_p.x > _b.x) {
                d[i] = get_d(_p,_b);
                continue;
            }
            d[i] = _p.y - _b.y;
            continue;
        }
        if(_p.y < _a.y) {
            if(_p.x > _b.x) {
                temp.x = _b.x;
                temp.y = _a.y;
                d[i] = get_d(_p,temp);
                continue;
            }
            if(_p.x < _a.x) {
                d[i] = get_d(_p,_a);
                continue;
            }
            d[i] = _a.y - _p.y;
            continue;
        }
        if(_p.x < _a.x) {
            d[i] = _a.x - _p.x;
            continue;
        }
        if(_p.x > _b.x) {
            d[i] = _p.x - _b.x;
            continue;
        }
        d[i] = 0;
    }

    double min;
    int j,k;
    for(i=1;i<=n;i++) {
        min = 99999999999999999;
        k = 0;
        for(j=1;j<=n;j++)
            if(!printed[j] && min > d[j]) {
                min = d[j];
                k = j;
            }
        printed[k] = 1;
        printf("%d ", k);
    }

return 0;}

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

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

Check is your sorting is stable