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

Tác giả: ladpro98

Ngôn ngữ: Pascal

{$N+}
program NKLAND;
uses    math;
const   maxn = 1009;
        fi = '';
type    Point = record
                x,y: double;
        end;
        Line = record
                a,b,c: double;
        end;
var     a, b:array[0..maxn] of Point;
        t, tt, i, j, m, n: longint;
        la, lb, lc: double;
        Distinct: boolean;
        inp, oup:text;

procedure Extract(p1, p2: Point; var a, b, c: double);
begin
        a := p1.y - p2.y;
        b := p2.x - p1.x;
        with p1 do c := -(a*x + b*y);
end;

function SameSide(a, b: Point): boolean;
begin
        exit((a.x*la+a.y*lb+lc)*(b.x*la+b.y*lb+lc) >= 0);
end;

begin
        assign(inp,fi);reset(inp);
        readln(inp,t);
        for tt:=1 to t do begin
                readln(inp,m);
                for i:=1 to m do read(inp,a[i].x,a[i].y);
                readln(inp,n);
                for i:=1 to n do read(inp,b[i].x,b[i].y);
                a[0] := a[m]; a[m+1] := a[1];

                for i:=1 to m do begin
                        Extract(a[i], a[i+1], la, lb, lc);
                        Distinct := true;
                        for j:=1 to n do
                        if SameSide(a[i-1], b[j]) then begin
                                Distinct := false;
                                break;
                        end;
                        if Distinct then break;
                end;
                if Distinct then writeln('NO')
                else writeln('YES');
        end;
end.

Download