ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1111. Квадраты

Why I get WA? Pelase, help me!!!!!!! Gave me any hints!! (+)
Послано Nazarov Denis (nsc2001@rambler.ru) 31 янв 2002 13:16
My program:

Program t1111;{$N+}

Const MaxN   = 100;
      Change = Pi/180;
      Eps    = 1E-14;
      Eps2   = 1E-12;

Type  Point  = record X,Y : extended end;
      Line   = record A,B,C : extended end; {Ax+By+C=0}
      Vector = record rX,rY : extended end;

Var   R      : array[1..MaxN,1..2]of Point;
      Dist   : array[1..MaxN]of extended;
      Pos    : array[1..MaxN]of integer;
      RV     : array[1..MaxN]of Vector;
      N,i,j  : integer;
      min,k  : integer;
      P      : Point;

Procedure Swap(Var A,B : integer);
Var t : integer;
 begin
  t:=A;
  A:=B;
  B:=t;
 end;

Function GetW(A : Vector) : extended;
Var tgW,W  : extended;
 begin
  if abs(A.rX)<Eps then begin
    if A.rY<0 then W:=270 else W:=90;
   end else
  if abs(A.rY)<Eps then begin
    if A.rX<0 then W:=180 else W:=0;
   end else begin
    tgW:=Abs(A.rY/A.rX);
    W:=ArcTan(tgW); W:=W/Change;
    if (A.rX<0)and(A.rY>0) then W:=180-W;
    if (A.rX<0)and(A.rY<0) then W:=180+W;
    if (A.rX>0)and(A.rY<0) then W:=360-W;
   end;
  GetW:=W;
 end;

Function RDist(A,B : Point) : extended;
 begin
  RDist:=Sqrt(Sqr(A.X-B.X)+Sqr(A.Y-B.Y));
 end;

Procedure MakeLine(M1,M2 : Point; Var L : Line);
Var A,B,C : extended;
 begin
  A:=M2.Y-M1.Y;
  B:=M1.X-M2.X;
  C:=-M1.X*A-M1.Y*B;
  L.A:=A; L.B:=B; L.C:=C;
 end;

Function GetDist(E1,E2 : Point) : extended;
Var CurLine         : Line;
    d1,d2,d,d3      : extended;
    Max,Min         : extended;
 begin
  if abs(E1.X-E2.X)<Eps then begin
     if E1.Y>E2.Y then begin
      Max:=E1.Y;
      Min:=E2.Y;
     end else begin
      Max:=E2.Y;
      Min:=E1.Y;
     end;
     d1:=RDist(E1,P);
     d2:=RDist(E2,P);
     d:=d1; if d2<d then d:=d2;
     if (P.Y>Min)and(P.Y<Max) then d:=abs(E1.X-P.X);
   end else
  if abs(E1.Y-E2.Y)<Eps then begin
     if E1.X>E2.X then begin
      Max:=E1.X;
      Min:=E2.X;
     end else begin
      Max:=E2.X;
      Min:=E1.X;
     end;
     d1:=RDist(E1,P);
     d2:=RDist(E2,P);
     d:=d1; if d2<d then d:=d2;
     if (P.X>Min)and(P.X<Max) then d:=abs(E1.Y-P.Y);
   end else begin
    MakeLine(E1,E2,CurLine);
    d1:=RDist(E1,P);
    d2:=RDist(E2,P);
    d:=d1; if d2<d then d:=d2;
    d3:=RDist(E1,E2);
    if d3*d3+d1*d1-d2*d2>Eps then
     if d3*d3+d2*d2-d1*d1>Eps then begin
      d1:=CurLine.A*P.X+CurLine.B*P.X+CurLine.C;
      d1:=abs(d1);
      d2:=sqrt(CurLine.A*CurLine.A+CurLine.B*CurLine.B);
      d:=d1/d2;
     end;
   end;
  GetDist:=d;
 end;

Procedure MakeDist(Num : integer);
Var W1,W2,W,len  : extended;
    V1,V2        : Vector;
    Ed1,Ed2      : Point;
    d1,d2,d3,d4  : extended;
 begin
  len:=RDist(R[Num,1],R[Num,2]);
  len:=len/sqrt(2);

  W:=GetW(RV[Num]);
  W1:=W+45; W1:=W1*Change;
   V1.rX:=cos(W1)*len;
   V1.rY:=sin(W1)*len;
  W2:=W-45; W2:=W2*Change;
   V2.rX:=cos(W2)*len;
   V2.rY:=sin(W2)*len;

  Ed1.X:=R[Num,2].X+V1.rX;
  Ed1.Y:=R[Num,2].Y+V1.rY;
  Ed2.X:=R[Num,2].X+V2.rX;
  Ed2.Y:=R[Num,2].Y+V2.rY;

  d1:=GetDist(R[Num,1],Ed1); len:=d1;
  d2:=GetDist(Ed1,R[Num,2]); if len>d2 then len:=d2;
  d3:=GetDist(R[Num,2],Ed2); if len>d3 then len:=d3;
  d4:=GetDist(Ed2,R[Num,1]); if len>d4 then len:=d4;

  d2:=RDist(Ed1,R[Num,2]);
  if abs(d1+d3-d2)<Eps2 then len:=0;

  Dist[Num]:=len;
 end;

begin
 Read(N);
 for i:=1 to N do Read(R[i,1].X,R[i,1].Y,R[i,2].X,R[i,2].Y);
 for i:=1 to N do begin
   RV[i].rX:=R[i,1].X-R[i,2].X;
   RV[i].rY:=R[i,1].Y-R[i,2].Y;
  end;
 Read(P.X,P.Y);
 for i:=1 to N do
  if (abs(RV[i].rX)<Eps)and(abs(RV[i].rY)<Eps) then
   Dist[i]:=RDist(R[i,1],P)
  else
   MakeDist(i);
 for i:=1 to N do Pos[i]:=i;
 for i:=1 to N-1 do begin
  min:=i;
  for j:=i+1 to N do
   if Dist[Pos[min]]-Dist[Pos[j]]<Ep