Unit Geom;
interface
Const
  MaxN=100000;
Type
  Pont=Record x,y:int64; az:Longint End;
  Szakasz=Record
            bal,jobb:Pont;
            az:Longint;
          End;
  PontHalmaz=Array[0..MaxN] of Pont;
  Sorozat=Array[0..MaxN] of 1..MaxN;

Function ForgasIrany(P0,P1,P2:Pont):Integer;
Function Szakaszon(p1,p2,q:Pont):Boolean;
Function Kozel(P0,P1,P2:Pont):Boolean;
Function Kozte(p1,p2,q:Pont):Boolean;
Procedure SarokRendez(Var P:Ponthalmaz; N:Longint);
Function GrahamKB(Var P:PontHalmaz; N:Longint):Longint;
Function SzakaszParMetsz(S1, S2:Szakasz):Boolean;
Function SzakaszMetsz(P1,P2,Q1,Q2:Pont):Boolean;
Function Ponthelyzete(Var P:PontHalmaz; N:Longint; Q:Pont):integer;
Function PolarRend(Q,P1,P2:Pont):Integer;
Function SarokRend(Q,P1,P2:Pont):Integer;

implementation

Function ForgasIrany(P0,P1,P2:Pont):Integer;
 {Kimenet: +1 ha P1-P2 balra fordul,
            0 ha P0,P1 ‰s P2 kollineßrisak,
           -1 ha P1-P2 jobbra fordul.}
Var
  KeresztSzorz:Int64;
Begin{ForgasIrany}
  KeresztSzorz:=(P1.x-P0.x)*(P2.y-P0.y)-(P2.x-P0.x)*(P1.y-P0.y);
  If (KeresztSzorz < 0) Then
    ForgasIrany:=-1
  Else If KeresztSzorz>0 Then
    ForgasIrany:=1
  Else
    ForgasIrany:=0;
End{ForgasIrany};

Function Szakaszon(p1,p2,q:Pont):Boolean;
Var Fir:Int64;
Begin
  Fir:=(p1.x-q.x)*(p2.y-q.y)-(p2.x-q.x)*(p1.y-q.y);
  Szakaszon:=(Fir=0)and (abs(q.x-p1.x)<=abs(p2.x-p1.x)) and
                        (abs(q.x-p2.x)<=abs(p2.x-p1.x)) and
                        (abs(q.y-p1.y)<=abs(p2.y-p1.y)) and
                        (abs(q.y-p2.y)<=abs(p2.y-p1.y)) ;
End;

Function Kozel(P0,P1,P2:Pont):Boolean;
{Feltétel: (p0,p1,p2) kollineáris ‚s p1,p2 a p0 azonos oldal n
 Kimenet: p1 közelebb van p0-hoz, mint p2
}
Begin
  Kozel:=(abs(p1.x-p0.x)<abs(p2.x-p0.x)) or
         (abs(p1.y-p0.y)<abs(p2.y-p0.y))
End;

Function Kozte(p1,p2,q:Pont):Boolean;
{Feltétel: (p1,p2,q) kollineáris
 Kimenet: q a p1 ‚s p2 k”z”tt van
}
Begin
  Kozte:=(abs(q.x-p1.x)<=abs(p2.x-p1.x)) and
         (abs(q.x-p2.x)<=abs(p2.x-p1.x)) and
         (abs(q.y-p1.y)<=abs(p2.y-p1.y)) and
         (abs(q.y-p2.y)<=abs(p2.y-p1.y))
End;

Function SzakaszParMetsz(S1, S2:Szakasz):Boolean;
Var
  fpq1,fpq2,fqp1,fqp2:integer;
Begin
  fpq1:=ForgasIrany(s1.bal,s1.jobb,s2.bal);
  fpq2:=ForgasIrany(s1.bal,s1.jobb,s2.jobb);
  fqp1:=ForgasIrany(s2.bal,s2.jobb,s1.bal);
  fqp2:=ForgasIrany(s2.bal,s2.jobb,s1.jobb);
SzakaszParMetsz:=(fpq1*fpq2<0) and (fqp1*fqp2<0)  or
	(fpq1=0)and Kozte(s1.bal,s1.jobb,s2.bal)  or
        (fpq2=0)and Kozte(s1.bal,s1.jobb,s2.jobb) or
        (fqp1=0)and Kozte(s2.bal,s2.jobb,s1.bal)  or
        (fqp2=0)and Kozte(s2.bal,s2.jobb,s1.jobb);
End;

Function SzakaszMetsz(P1,P2,Q1,Q2:Pont):Boolean;
Var
  fpq1,fpq2,fqp1,fqp2:integer;
Begin
  fpq1:=ForgasIrany(p1,p2,q1);
  fpq2:=ForgasIrany(p1,p2,q2);
  fqp1:=ForgasIrany(q1,q2,p1);
  fqp2:=ForgasIrany(q1,q2,p2);
SzakaszMetsz:=(fpq1*fpq2<0) and (fqp1*fqp2<0)   or
	(fpq1=0)and Kozte(p1,p2,q1) or
        (fpq2=0)and Kozte(p1,p2,q2) or
        (fqp1=0)and Kozte(q1,q2,p1) or
        (fqp2=0)and Kozte(q1,q2,p2);
End;
Function Tav(P1, P2:Pont):double;
Begin
  Tav:=Sqrt(Sqr(p1.x-p2.x)+Sqr(p1.y-p2.y));
End;

Procedure SarokRendez(Var P:Ponthalmaz; N:Longint);
  Var
    i,i0 : Longint;
    Q : Pont;

  Function Megelozi(x,y:Pont):Boolean;
  {A (Q,P[i]) sz÷g kisebb, mint a (Q,P[j]) sz÷g?}
  Begin{Megelozi}
     Megelozi:=SarokRend(P[0],x,y)=-1
  End{Megelozi};

  Procedure Sullyeszt(K,L : Longint );
  {Input : P[K+1..L] kupac,  Output: P[K..L] kupac   }
    Var  Apa,Fiu : Longint;
      E:Pont;
    Begin{Sullyeszt}
      E:=P[K]; Apa:=K; Fiu:=2*Apa;
      While (Fiu <= L) Do Begin
        If (Fiu < L) And Megelozi(P[Fiu],P[Fiu+1]) Then
          Fiu := Fiu+1;
        If Not Megelozi(E, P[Fiu]) Then
          Break
        Else Begin
          P[Apa]:=P[Fiu];
          Apa:=Fiu; Fiu:=2*Apa
        End
      End{while};
      P[Apa] := E
    End{Sullyeszt};

  Begin{SarokRendez}
    i0:=0;
    {a sarokpont meghatßrozßsa}
    For i:=1 To N-1 Do Begin
      If (P[i].x<P[i0].x)Or
         ((P[i].x=P[i0].x)And(P[i].y<P[i0].y)) Then
        i0:=i
    End{for i};
    Q:=P[i0]; P[i0]:=P[0]; P[0]:=Q;

    For i :=(N-1) Div 2 Downto 1 Do  Sullyeszt(i, N-1);{Kupacépít}
    For i := N-1 Downto 2 Do Begin
      Q:=P[i]; P[i]:=P[1]; P[1]:=Q;
      Sullyeszt(1,i-1)
    End{for i};
End{SarokRendez};

Function GrahamKB(Var P:PontHalmaz; N:Longint):Longint;
{Bemenet: P[1],...,P[N],
 Kimenet: P[1],...,P[M] a konvex burok csŁcsai }
Var
  m,i:Longint;
  xy:Pont;
Begin{KonvexBurok}
  SarokRendez(P,N);
  M:=2;
  For i:=3 To N-1 Do Begin
    While (m>2)And(ForgasIrany(P[m-1], P[m], P[i])<=0) Do
      Dec(m);
    Inc(m);
    xy:=P[m]; P[m]:=P[i]; P[i]:=xy;
  End{for};
  GrahamKB:=m;
End{KonvexBurok};

Function PolarRend(Q,P1,P2:Pont):Integer;
{A Q ponthoz viszonyˇtott pol rsz”g szerint rendez‚sben P1 ‚s P2 viszonya;
}
Var
  Fir:Integer;
Begin
  If (P1.x=P2.x)and(P1.y=P2.y) Then begin
    PolarRend:=0;
    Exit;
  End;
  Fir:=Forgasirany(Q,P1,P2);
  Case Fir of
    -1: If (p1.y<=q.y) and (p2.y>q.y) Then
          PolarRend:=-1
        Else
          PolarRend:=1;
    0 : If Kozte(q,p2,p1) or
           Kozte(p1,p2,q)and ((p1.y<q.y) or (p1.y=q.y)and(p1.x<q.x))
        Then
          PolarRend:=-1
        Else
          PolarRend:=1;
    +1: If (p1.y<=q.y) or (p2.y>q.y) Then
          PolarRend:=-1
        Else
          PolarRend:=1;
  End{case};
End{PolarRend};

Function SarokRend(Q,P1,P2:Pont):Integer;
{A Q bal-als˘ sarokponthoz viszonyˇtott pol rsz”g szerint rendez‚sben P1 ‚s P2 viszonya;
}
Var Fir:Integer;
Begin
  If (P1.x=P2.x)and(P1.y=P2.y) Then begin
    SarokRend:=0;
    Exit;
  End;
  Fir:=Forgasirany(Q,P1,P2);
  If (Fir>0) or (Fir=0)and(Kozel(Q,P1,P2)) Then
    SarokRend:=-1
  Else
    SarokRend:=1;
End{SarokRend};

Function Ponthelyzete(Var P:PontHalmaz; N:Longint; Q:Pont):integer;
Var y0,x0:Int64;
  i,ii,metsz:Longint;
  q0:POnt;
Begin
  Ponthelyzete:=0;
  y0:=q.y;
  x0:=P[1].x;
  for i:=1 To n do Begin
    if (P[i].y<q.y)and ((P[i].y>y0) or (y0=q.y) )  then
      y0:=P[i].y;
   if (P[i].x<x0) then x0:=P[i].x;
  end{for};
  if (y0=q.y) then begin Ponthelyzete:=1; exit end;
  q0.y:=y0; q0.x:=x0-1;
  metsz:=0;
  for i:=1 to n do begin
    ii:=(i+1)mod n;
    if (Szakaszon(P[i], P[ii], q) ) then exit;
    if (ForgasIrany(P[i],P[ii],q0)*ForgasIrany(P[i],P[ii],q)<0) and
       (ForgasIrany(q0, q, P[i])*ForgasIrany(q0, q, P[ii]) <0 ) then
    Inc(metsz);
   if (metsz mod 2 =0) then
     Ponthelyzete:=1
   else
     Ponthelyzete:=-1;
   end{for i}
End{ Ponthelyzete};

End.