NKLAND - Mảnh đất tổ tiên

Tác giả: RR

Ngôn ngữ: Pascal

//Written by RR
{$ifdef rr}
  {$r+,q+}
  {$mode objfpc}
  {$inline off}
{$else}
  {$r-,q-}
  {$mode objfpc}
  {$inline on}
{$endif}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       1111;
  alpha         =       pi/4;
type
  real          =       extended;
  point         =       record x,y:real; end;
var
  f1,f2         :       text;
  n1,n2,test    :       longint;
  a,b           :       array[1..MAXN] of point;
  sina,cosa,now :       real;
  ln,nn         :       real;
  intersect     :       boolean;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure quay(var a:point); inline;
    var
      u:point;
    begin
      u:=a;
      a.x:=u.x*cosa-u.y*sina;
      a.y:=u.y*cosa+u.x*sina;
    end;

begin
  openF;
  read(f1,test);
  sina:=sin(alpha); cosa:=cos(alpha);
  for test:=1 to test do
    begin
      read(f1,n1);
      for n1:=1 to n1 do
        with a[n1] do read(f1,x,y);
      read(f1,n2);
      for n2:=1 to n2 do
        with b[n2] do read(f1,x,y);
      now:=0;
      intersect:=true;
      while (now<=3.15) do
        begin
          now+=alpha;
          for n1:=1 to n1 do
            quay(a[n1]);
          for n2:=1 to n2 do
            quay(b[n2]);
          ln:=-2000111000; nn:=-ln;
          for n1:=1 to n1 do
            ln:=max(ln,a[n1].x);
          for n2:=1 to n2 do
            nn:=min(nn,b[n2].x);
          if ln<nn then
            begin
              writeln(f2,'NO');
              intersect:=false;
              break;
            end;
          ln:=-2000111000; nn:=-ln;
          for n1:=1 to n1 do
            nn:=min(nn,a[n1].x);
          for n2:=1 to n2 do
            ln:=max(ln,b[n2].x);
          if ln<nn then
            begin
              writeln(f2,'NO');
              intersect:=false;
              break;
            end;
        end;
      if intersect then writeln(f2,'YES');
    end;
  closeF;
end.

Download