program ksp2512;

type
    TBod = record
        X, Y : integer;
    end;

    POkraj = ^TOkraj;    {seznam vrcholů na levém, či pravém okraji mnohoúhelníku}
    TOkraj = record
        Levy : boolean;
        AktualniPozice : integer;
        Vrcholy : array of TBod;
        Mnohouhelnik : integer;
    end;

    {Události - co se bude dít na sweep-line}
    TTypUdalosti = (U_ODSTRAN_STANEK, U_VRCHOL_STANKU, U_PRIDEJ_STANEK);
        {Seřazeno aby se nejdřív odebíralo, pak měnilo a nakonec přidávalo}
    TUdalost = record
        Jaka : TTypUdalosti;
        YSouradnice : integer;
        Okraj1, Okraj2 : POkraj; {u vrcholu je vyplněn jen první}
    end;

    PHalda = ^THalda;     {Halda - vlastní implementace prioritní fronty}
    THalda = record
        Udalost : TUdalost;
        LevySyn, PravySyn, Otec : PHalda; {"Klasické" části haldy}
        PredchoziVrchol, DalsiVrchol : PHalda;
        {lineární spojový seznam po hladinách haldy, užit k přidávání/ubírání}
    end;

    TPrioritniFronta = record
        KorenHaldy : PHalda;
        PosledniVrchol : PHalda;
    end;

    Mnohouhelnik = record {jak budeme mít každý stánek popsaný}
        Vrcholy : array of TBod;
        LevyOkraj, PravyOkraj : TOkraj;
        MinY, MaxY : integer;
    end;

    PIntervalovyAVLStrom = ^TIntervalovyAVLStrom;
        {Užit k vyhledávání, jestli daná linie je uvnitř jiného mnohoúhelníku}
    TIntervalovyAVLStrom = record
        Obsah : POkraj;{Vlastní obsah vrcholu, synové jsou od něj na příslušnou stranu (i geometricky)}
        LevySyn, PravySyn : PIntervalovyAVLStrom;
        HloubkaVrcholu : integer; {vzdálenost od nejvzdálenějšího listu}
    end;

var Stanky : array of Mnohouhelnik; {vlastní informace o stáncích}
    Intervaly : PIntervalovyAVLStrom;
        {průběžně aktualizované informace o tom, které intervaly (v X směru) patří do kterého stánku}
    NalezenaKolize : boolean; {pokud se nastaví, někde jsme malezli překrývající se stánky}
    Fronta : TPrioritniFronta; {Co se bude dále dít na sweep-line}
    Udalost : TUdalost;

procedure Nacti;   {jen načtení vstupu}
var Stanku, Bodu : integer;
    s, b : integer;
begin
    readln(Stanku);
    SetLength(Stanky, Stanku);
    for s:=0 to Stanku-1 do begin
        readln(Bodu);
        SetLength(Stanky[s].Vrcholy, Bodu);
        for b:=0 to Bodu-1 do readln(Stanky[s].Vrcholy[b].X, Stanky[s].Vrcholy[b].Y);
    end;
end;

function VektSoucin(X1, Y1, X2, Y2 : integer) : integer; {z-složka vektorového součinu}
begin
    VektSoucin := X1*Y2 - Y1*X2;
end;

procedure NajdiOkraje; {rozdělí obvod mnohoúhelníku na levý a pravý okraj (z hlediska osy Y)}
                       {předpokládá, že načtené body na obvodu mnohoúhelníku jsou unikátní}
var Stanek, Bod, i : integer;
    MinYVrchol : integer;
    DalsiVrchol, PredchoziVrchol : integer;
    PoSmeruRucicek : boolean;
    Temp : TBod;
    LevyZac, LevyKon, VlevoVrcholu, PravyZac, PravyKon, VpravoVrcholu : integer;
begin
    for Stanek:=0 to length(Stanky)-1 do with Stanky[Stanek] do begin
        MinY := Vrcholy[0].Y;  {nejnižší a nejvyšší Y, kam mnohoúhelník zasahuje}
        MinYVrchol := 0;       {a u nejnižšího si zapamatujeme i který vrchol to byl}
        MaxY := Vrcholy[0].Y;
        for Bod:=1 to length(Vrcholy)-1 do begin
            if Vrcholy[Bod].Y>MaxY then MaxY := Vrcholy[Bod].Y;
            if Vrcholy[Bod].Y<=MinY then begin
                MinYVrchol := Bod;
                MinY := Vrcholy[Bod].Y;
            end;
        end;
        {nyní najdeme první poslední vrchol (indexem), který má ještě má minimální souřadnici Y}
        DalsiVrchol := MinYVrchol;
        repeat
            LevyZac := DalsiVrchol;
            DalsiVrchol := (DalsiVrchol+1) mod length(Vrcholy);
        until Vrcholy[DalsiVrchol].Y>MinY;
        PredchoziVrchol := (LevyZac+length(Vrcholy)-1) mod length(Vrcholy);
        {a pomocí vektorového součinu zjistíme orientaci zadání - po či proti směru hodinových ručiček}
        PoSmeruRucicek := VektSoucin(
          Vrcholy[LevyZac].X-Vrcholy[PredchoziVrchol].X, Vrcholy[LevyZac].Y-Vrcholy[PredchoziVrchol].Y,
          Vrcholy[DalsiVrchol].X-Vrcholy[LevyZac].X, Vrcholy[DalsiVrchol].Y-Vrcholy[LevyZac].Y)<0;
        if not PoSmeruRucicek then begin {obrátíme pořadí}
            for Bod:=0 to (length(Vrcholy) div 2) - 1 do begin
                Temp := Vrcholy[length(Vrcholy)-1-Bod];
                Vrcholy[length(Vrcholy)-1-Bod] := Vrcholy[Bod];
                Vrcholy[Bod] := Temp;
            end;
            MinYVrchol := length(Vrcholy)-1-MinYVrchol; {a opravíme pozici začátku levého okraje}
            DalsiVrchol := MinYVrchol;
            repeat
                LevyZac := DalsiVrchol;
                DalsiVrchol := (DalsiVrchol+1) mod length(Vrcholy);
            until Vrcholy[DalsiVrchol].Y>MinY;
        end;
        LevyKon := LevyZac; {najdeme konec levého kraje a zjistíme kolik ho tvoří vrcholů}
        VlevoVrcholu := 1;
        repeat
            LevyKon := (LevyKon+1) mod length(Vrcholy);
            inc(VlevoVrcholu);
        until Vrcholy[LevyKon].Y=MaxY;
        DalsiVrchol := LevyKon; {pak najdeme pozici pravého okraje}
        repeat
            PravyKon := DalsiVrchol;
            DalsiVrchol := (DalsiVrchol+1) mod length(Vrcholy);
        until Vrcholy[DalsiVrchol].Y<MaxY;
        PravyZac := PravyKon; {a v zápětí jeho konec a i počet vrcholů, které ho tvoří}
        VpravoVrcholu := 1;
        repeat
            PravyZac := (PravyZac+1) mod length(Vrcholy);
            inc(VpravoVrcholu);
        until Vrcholy[PravyZac].Y=MinY;
        SetLength(LevyOkraj.Vrcholy, VlevoVrcholu); {Okopírování příslušné skupiny vrcholů odspodu}
        LevyOkraj.Levy := true;
        LevyOkraj.Mnohouhelnik := Stanek;
        Bod := LevyZac;
        for i:=0 to VlevoVrcholu-1 do begin
            LevyOkraj.Vrcholy[i] := Vrcholy[Bod];
            Bod:=(Bod+1) mod length(Vrcholy);
        end;
        SetLength(PravyOkraj.Vrcholy, VpravoVrcholu); {Okopírování příslušné skupiny vrcholů odspodu}
        PravyOkraj.Levy := false;
        PravyOkraj.Mnohouhelnik := Stanek;
        Bod := PravyZac;
        for i:=0 to VpravoVrcholu-1 do begin
            PravyOkraj.Vrcholy[i] := Vrcholy[Bod];
            Bod := (Bod+length(Vrcholy)-1) mod length(Vrcholy);
        end;
    end;
end;

type TPorovnani = (POR_VLEVO, POR_VPRAVO, POR_IDENTICKE, POR_KOLIZE);

function PorovnejOkraje(Ktery, SCim : POkraj) : TPorovnani; {porovná vzájemnou polohu okrajů}
var YDolni, YHorni : integer; {dolní a horní okraj překryvu v Y směru}
    DolniPoloha, HorniPoloha : integer;
    PrvniUsecka, DruhaUsecka : record
                                   Zacatek, Konec : TBod;
                                   DeltaX, DeltaY : integer;
                               end;
begin
    {pro zjednodušení si přepíšeme prvni a druhou aktualní úsečku}
    PrvniUsecka.Zacatek :=Ktery^.Vrcholy[Ktery^.AktualniPozice];
    PrvniUsecka.Konec := Ktery^.Vrcholy[Ktery^.AktualniPozice+1];
    PrvniUsecka.DeltaX := PrvniUsecka.Konec.X - PrvniUsecka.Zacatek.X;
    PrvniUsecka.DeltaY := PrvniUsecka.Konec.Y - PrvniUsecka.Zacatek.Y;
    DruhaUsecka.Zacatek := SCim^.Vrcholy[SCim^.AktualniPozice];
    DruhaUsecka.Konec := SCim^.Vrcholy[SCim^.AktualniPozice+1];
    DruhaUsecka.DeltaX := DruhaUsecka.Konec.X - DruhaUsecka.Zacatek.X;
    DruhaUsecka.DeltaY := DruhaUsecka.Konec.Y - DruhaUsecka.Zacatek.Y;
    {nyní určíme Y rozsah, kde jsou definované obě úsečky}
    if PrvniUsecka.Zacatek.Y>DruhaUsecka.Zacatek.Y then YDolni := PrvniUsecka.Zacatek.Y
    else YDolni := DruhaUsecka.Zacatek.Y;
    if PrvniUsecka.Konec.Y<DruhaUsecka.Konec.Y then YHorni := PrvniUsecka.Konec.Y
    else YHorni := DruhaUsecka.Konec.Y;
    {a dopočteme relativní polohy na dolním a horním okraji}
    DolniPoloha := PrvniUsecka.DeltaY*DruhaUsecka.DeltaY*(DruhaUsecka.Zacatek.X-PrvniUsecka.Zacatek.X)
                  +PrvniUsecka.DeltaY*DruhaUsecka.DeltaX*(YDolni-DruhaUsecka.Zacatek.Y)
                  -PrvniUsecka.DeltaX*DruhaUsecka.DeltaY*(YDolni-PrvniUsecka.Zacatek.Y);
    HorniPoloha := PrvniUsecka.DeltaY*DruhaUsecka.DeltaY*(DruhaUsecka.Zacatek.X-PrvniUsecka.Zacatek.X)
                  +PrvniUsecka.DeltaY*DruhaUsecka.DeltaX*(YHorni-DruhaUsecka.Zacatek.Y)
                  -PrvniUsecka.DeltaX*DruhaUsecka.DeltaY*(YHorni-PrvniUsecka.Zacatek.Y);
    if DolniPoloha>0 then begin {Na dolním okraji je "Ktery" vlevo od "SCim"}
        if HorniPoloha>=0 then PorovnejOkraje := POR_VLEVO {nahoře je "Ktery" vlevo od "SCim"}
        else PorovnejOkraje := POR_KOLIZE; {Dole vlevo, nahoře vpravo ...}
    end else if DolniPoloha=0 then begin {Na dolním okraji splývá "Ktery" s "SCim"}
        if HorniPoloha>0 then PorovnejOkraje := POR_VLEVO {nahoře vlevo, dole splývají}
        else if HorniPoloha<0 then PorovnejOkraje := POR_VPRAVO {nahoře vpravo, dole splývají}
        else begin {nahoře splývají, dole splývají}
            if Ktery=SCim then PorovnejOkraje := POR_IDENTICKE {ten samý okraj}
            else if Ktery^.Levy then begin
                if SCim^.Levy then PorovnejOkraje := POR_KOLIZE {oba okraje jsou levé => bude překryv}
                else PorovnejOkraje := POR_VPRAVO; {při dotyku levý okraj patří vpravo od pravého}
            end else begin
                if SCim^.Levy then PorovnejOkraje := POR_VLEVO{dotyk - levý okraj je vpravo od pravého}
                else PorovnejOkraje := POR_KOLIZE; {dva pravé okraje => bude překryv}
            end;
        end;
    end else begin {Na dolním okraji je "Ktery" vpravo od "SCim"}
        if HorniPoloha<=0 then PorovnejOkraje := POR_VPRAVO {nahoře je "Ktery" vpravo od "SCim"}
        else PorovnejOkraje := POR_KOLIZE; {Dole vpravo, nahoře vlevo ...}
    end;
end;

function Max(C1, C2 : integer) : integer; {maximum - pro zkrácení zápisů}
begin
    if (C1>C2) then Max := C1 else Max := C2;
end;

function Hloubka(Vrchol : PIntervalovyAVLStrom) : integer; {vrátí hloubku vrcholu, pokud neexistuje -1}
begin
    if Vrchol=nil then Hloubka := -1 else Hloubka := Vrchol^.HloubkaVrcholu;
end;

procedure NormalizujAVL(var Vrchol : PIntervalovyAVLStrom);
{synové se (možná) změnili - přepočítá se hloubka a případně provede rotace}
var LevaHloubka, PravaHloubka : integer;
    X, Y, B : PIntervalovyAVLStrom;
{    A, C : PIntervalovyAVLStrom;}
begin
    LevaHloubka := Hloubka(Vrchol^.LevySyn);
    PravaHloubka := Hloubka(Vrchol^.PravySyn);
    Vrchol^.HloubkaVrcholu := Max(LevaHloubka,PravaHloubka)+1;
    {přepočtena hloubka vrcholu}
    if Vrchol^.HloubkaVrcholu-LevaHloubka > 2 then begin {Pravá strana je příliš hluboká}
        if Hloubka(Vrchol^.PravySyn^.LevySyn) > Hloubka(Vrchol^.PravySyn^.PravySyn) then begin
        {hlubší je pravo-levý vnuk, protočíme aby byl hlubší pravo-pravý}
            Y := Vrchol^.PravySyn;
            X := Y^.LevySyn;
{            A := X^.LevySyn;}
            B := X^.PravySyn;
{            C := Y^.PravySyn;}
{            X^.LevySyn := A;}
            X^.PravySyn := Y;
            Y^.LevySyn := B;
{            Y^.PravySyn := C;}
            Vrchol^.PravySyn := X;
            Y^.HloubkaVrcholu := Max(Hloubka(Y^.LevySyn), Hloubka(Y^.PravySyn)) + 1;
            X^.HloubkaVrcholu := Max(Hloubka(X^.LevySyn), Hloubka(X^.PravySyn)) + 1;
        end; {provedena rotace a opraveny hloubky}
        Y := Vrchol;
        X := Y^.PravySyn;
{        A := Y^.LevySyn;}
        B := X^.LevySyn;
{        C := X^.PravySyn;}
{        Y^.LevySyn := A;}
        Y^.PravySyn := B;
        X^.LevySyn := Y;
{        X^.PravySyn := C;}
        Vrchol := X;
        Y^.HloubkaVrcholu := Max(Hloubka(Y^.LevySyn), Hloubka(Y^.PravySyn)) + 1;
        X^.HloubkaVrcholu := Max(Hloubka(X^.LevySyn), Hloubka(X^.PravySyn)) + 1;
    end else if Vrchol^.HloubkaVrcholu-PravaHloubka>2 then begin {Levá strana je příliš hluboká}
        if Hloubka(Vrchol^.LevySyn^.PravySyn) > Hloubka(Vrchol^.LevySyn^.LevySyn) then begin
        {hlubší je levo-pravý vnuk, protočíme aby byl hlubší levo-levý}
            Y := Vrchol^.LevySyn;
            X := Y^.PravySyn;
{            A := X^.PravySyn;}
            B := X^.LevySyn;
{            C := Y^.LevySyn;}
{            X^.PravySyn := A;}
            X^.LevySyn := Y;
            Y^.PravySyn := B;
{            Y^.LevySyn := C;}
            Vrchol^.LevySyn := X;
            Y^.HloubkaVrcholu := Max(Hloubka(Y^.LevySyn), Hloubka(Y^.PravySyn)) + 1;
            X^.HloubkaVrcholu := Max(Hloubka(X^.LevySyn), Hloubka(X^.PravySyn)) + 1;
        end; {provedena rotace a opraveny hloubky}
        Y := Vrchol;
        X := Y^.LevySyn;
{        A := Y^.PravySyn;}
        B := X^.PravySyn;
{        C := X^.LevySyn;}
{        Y^.PravySyn := A;}
        Y^.LevySyn := B;
        X^.PravySyn := Y;
{        X^.LevySyn := C;}
        Vrchol := X;
        Y^.HloubkaVrcholu := Max(Hloubka(Y^.LevySyn), Hloubka(Y^.PravySyn)) + 1;
        X^.HloubkaVrcholu := Max(Hloubka(X^.LevySyn), Hloubka(X^.PravySyn)) + 1;
    end;
end;

function PridejDoAVLStromu(var Strom : PIntervalovyAVLStrom; Okraj : POkraj) : boolean;
{Přidá vrchol do interalového stromu}
{Okraj - co se má přídat a Y je aktuální pozice sweep-line}
{vraci true, pokud bylo uspesne pridano}
var Pridano : boolean;
begin
    if Strom=nil then begin {nový vrchol}
        new(Strom);
        Strom^.LevySyn := nil;
        Strom^.PravySyn := nil;
        Strom^.Obsah := Okraj;
        Strom^.HloubkaVrcholu := 0; {list}
        PridejDoAVLStromu := true;  {vytvořen list, jsme hotovi}
    end else begin
        Pridano := false;
        case PorovnejOkraje(Okraj,Strom^.Obsah) of
            POR_VLEVO : Pridano := PridejDoAVLStromu(Strom^.LevySyn, Okraj);{patří levému podstromu}
            POR_VPRAVO : Pridano := PridejDoAVLStromu(Strom^.PravySyn, Okraj);{patří pravému podstromu}
            POR_IDENTICKE : ; {už tu je, 2x ho vkládat nebudeme. Sem by se program neměl dostat}
            POR_KOLIZE : NalezenaKolize:=true; {kolize - nevložíme a oznámíme to}
        end;
        if Pridano then NormalizujAVL(Strom);
        PridejDoAVLStromu := Pridano; {Pokud proběhla změna zkontrolujeme normalizaci "po cestě"}
    end;
end;

function OdeberZAVLStromu(var Strom : PIntervalovyAVLStrom; Okraj : POkraj) : boolean;
{odebere vrchol z intervalového stromu, vrací true pokud odebrání proběhlo v pořádku}
{Okraj - co se má odebrat}
var Zmeneno : boolean;
    Vrchol  :PIntervalovyAVLStrom;
begin
    if Strom=nil then OdeberZAVLStromu := false {nenalezeno}
    else if (Strom^.LevySyn=nil) and (Strom^.PravySyn=nil) then begin {list}
        if Strom^.Obsah=Okraj then begin
            dispose(Strom); {zahodíme list}
            Strom := nil;
            OdeberZAVLStromu := true;
        end else OdeberZAVLStromu := false; {nenalezeno}
    end else begin
        Zmeneno := false;
        case PorovnejOkraje(Okraj, Strom^.Obsah) of
            POR_VLEVO : Zmeneno := OdeberZAVLStromu(Strom^.LevySyn, Okraj);   {je v levém podstromě}
            POR_VPRAVO : Zmeneno := OdeberZAVLStromu(Strom^.PravySyn, Okraj); {je v pravém podstromě}
            POR_IDENTICKE : if Strom^.LevySyn=nil then begin {identita a neexistuje levý syn}
                    Vrchol := Strom^.PravySyn; {nahradíme pravým synem}
                    dispose(Strom);
                    Strom := Vrchol;
                    Zmeneno := true;
                end else begin {identita a levý syn existuje}
                    Vrchol := Strom^.LevySyn; {najdeme nejpravější okraj vlevo od odstraňovaného}
                    while Vrchol^.PravySyn<>nil do Vrchol := Vrchol^.PravySyn;
                    Strom^.Obsah := Vrchol^.Obsah; {prohodíme obsah, čímž nenarušíme strom}
                    Vrchol^.Obsah := Okraj; {jelikož víme, že originální Strom^.Obsah = Okraj}
                    Zmeneno := OdeberZAVLStromu(Strom^.LevySyn, Okraj); {a odebereme rekurzivně}
                end;
            POR_KOLIZE : ; {sem by se program dostat neměl - odebíráme jen to, co jsme přidali}
        end;
        if Zmeneno then NormalizujAVL(Strom);
        OdeberZAVLStromu := Zmeneno;
    end;
end;

function NejblizsiLevyOkraj(Strom:PIntervalovyAVLStrom; KCemu:POkraj) : POkraj;
{najde nejbližší levý okraj k zadanému bodu}
var LevyLimit : POkraj;
begin
    LevyLimit := nil;
    while Strom<>nil do begin
        case PorovnejOkraje(Strom^.Obsah, KCemu) of
            POR_VLEVO : begin
                    {"strom" je vlevo ... posuneme se a zapíšeme nového (bližšího) pravého souseda}
                    LevyLimit := Strom^.Obsah;
                    Strom := Strom^.PravySyn;
                end;
            POR_VPRAVO : Strom := Strom^.LevySyn;
                    {"strom" je vpravo ... posuneme se a zapíšeme nového (bližšího) levého souseda}
            POR_KOLIZE : begin {kolize}
                    NalezenaKolize := true;
                    break;
                end;
            POR_IDENTICKE : begin {sem by se dostat neměl}
                    LevyLimit := Strom^.Obsah;
                    Strom := Strom^.PravySyn;
                end;
        end;
    end;
    NejblizsiLevyOkraj := LevyLimit;
end;

function JeDriv(Udalost, SCim:TUdalost) : boolean;
{porovná kdy nastane a vrátí true, pokud UDALOST se musí vyřídit dřív}
begin
    if Udalost.YSouradnice=SCim.YSouradnice then
        JeDriv := (Udalost.Jaka<SCim.Jaka)
        {díky setřízení nejdřív odebereme, pak opravíme okraje a nakonec přidáme nové stánky}
    else JeDriv := (Udalost.YSouradnice<SCim.YSouradnice);
end;

procedure PridejDoPrioritniFronty(var Fronta:TPrioritniFronta; Udalost:TUdalost);
{přidá událost do prioritní fronty}
var Vrchol : PHalda;
    Temp : TUdalost;
begin
    new(Vrchol);
    Vrchol^.Udalost := Udalost;
    Vrchol^.LevySyn := nil;
    Vrchol^.PravySyn := nil;
    Vrchol^.DalsiVrchol := nil;
    Vrchol^.PredchoziVrchol := Fronta.PosledniVrchol;
    if Fronta.PosledniVrchol=nil then begin {první vrchol ve frontě}
        Vrchol^.Otec := nil;
        Fronta.KorenHaldy := Vrchol;
    end else if Fronta.PosledniVrchol^.Otec=nil then begin {druhý vrchol}
        Vrchol^.Otec := Fronta.PosledniVrchol;
        Fronta.PosledniVrchol^.LevySyn := Vrchol;
    end else begin
        Vrchol^.PredchoziVrchol := Fronta.PosledniVrchol;
        if Fronta.PosledniVrchol^.Otec^.PravySyn=nil then begin
            {otec předchozího posledního vrcholu ještě nemá pravého syna}
            Vrchol^.Otec := Fronta.PosledniVrchol^.Otec; {přidáme se na toto místo}
            Vrchol^.Otec^.PravySyn := Vrchol;
        end else begin {otec předchozího vrcholu má oba syny, přidáme se na místo jeho pravého souseda}
            Vrchol^.Otec := Fronta.PosledniVrchol^.Otec^.DalsiVrchol;
            Vrchol^.Otec^.LevySyn := Vrchol;
        end;
    end;
    if Fronta.PosledniVrchol<>nil then Fronta.PosledniVrchol^.DalsiVrchol := Vrchol;
    Fronta.PosledniVrchol := Vrchol; {tohle je nový poslední vrchol}
    Vrchol := Vrchol^.Otec;
    while (Vrchol<>nil) do begin {opravíme případné problémy}
        if not JeDriv(Vrchol^.Udalost, Vrchol^.LevySyn^.Udalost) then begin {levý syn je dřív}
            Temp := Vrchol^.Udalost;                                        {=> prohodíme}
            Vrchol^.Udalost := Vrchol^.LevySyn^.Udalost;
            Vrchol^.LevySyn^.Udalost := Temp;
        end;
        if Vrchol^.PravySyn<>nil then
         if not JeDriv(Vrchol^.Udalost, Vrchol^.PravySyn^.Udalost) then begin
            {pravý syn nastal dřív => prohodíme}
            Temp := Vrchol^.Udalost;
            Vrchol^.Udalost := Vrchol^.PravySyn^.Udalost;
            Vrchol^.PravySyn^.Udalost := Temp;
        end;
        Vrchol := Vrchol^.Otec;
    end;
end;

procedure OdstranKorenPrioritniFronty(var Fronta : TPrioritniFronta); {Odstraní první událost na řadě}
var Vrchol : PHalda;
    Temp : TUdalost;
    LevyJeDriv : boolean;
begin
    if (Fronta.KorenHaldy=Fronta.PosledniVrchol) then begin {máme už jen kořen haldy}
        dispose(Fronta.KorenHaldy);
        Fronta.KorenHaldy := nil;
        Fronta.PosledniVrchol := nil;
    end else begin
        Vrchol := Fronta.PosledniVrchol;
        Fronta.KorenHaldy^.Udalost := Vrchol^.Udalost; {nakopírujeme sem událost z posledního vrcholu}
        if Vrchol^.Otec^.LevySyn=Vrchol then Vrchol^.Otec^.LevySyn := nil;
        if Vrchol^.Otec^.PravySyn=Vrchol then Vrchol^.Otec^.PravySyn := nil;
            {odstraníme záznam, že tento syn v haldě existuje}
        Vrchol^.PredchoziVrchol^.DalsiVrchol := nil;
        Fronta.PosledniVrchol := Vrchol^.PredchoziVrchol; {opravíme lineární spojový seznam}
        dispose(Vrchol); {a odstraníme vlastní vrchol}
        Vrchol := Fronta.KorenHaldy; {vrchol, kde může být problém}
        while Vrchol^.LevySyn<>nil do begin {dokud má nějaké syny ...}
            if Vrchol^.PravySyn<>nil then {zjistíme, který ze synů je třeba zpracovat dřív}
                LevyJeDriv := JeDriv(Vrchol^.LevySyn^.Udalost, Vrchol^.PravySyn^.Udalost)
            else LevyJeDriv := true; {pravý neexistuje, budeme porovnávat jen s levým}
            if LevyJeDriv then begin {porovnáváme s levým podstromem}
                if JeDriv(Vrchol^.LevySyn^.Udalost, Vrchol^.Udalost) then begin
                    {je třeba prohodit a pokračovat s levým podstromem?}
                    Temp := Vrchol^.LevySyn^.Udalost;
                    Vrchol^.LevySyn^.Udalost := Vrchol^.Udalost;
                    Vrchol^.Udalost := Temp;
                    Vrchol := Vrchol^.LevySyn;
                end else break; {už je vše srovnáno}
            end else begin {porovnáváme s pravým podstromem}
                if JeDriv(Vrchol^.PravySyn^.Udalost, Vrchol^.Udalost) then begin
                    {je třeba prohodit a pokračovat s pravým podstromem?}
                    Temp := Vrchol^.PravySyn^.Udalost;
                    Vrchol^.PravySyn^.Udalost := Vrchol^.Udalost;
                    Vrchol^.Udalost := Temp;
                    Vrchol := Vrchol^.PravySyn;
                end else break; {už je vše srovnáno}
            end;
        end;
    end;
end;

procedure PridejOkrajeStanku(var Fronta : TPrioritniFronta);
{přidá do fronty událostí kde jsou okraje stánků}
var Stanek : integer;
    Udalost : TUdalost;
begin
    for Stanek:=0 to length(Stanky)-1 do begin
        Udalost.Jaka := U_PRIDEJ_STANEK;
        Udalost.YSouradnice := Stanky[Stanek].MinY;
        Udalost.Okraj1 := @(Stanky[Stanek].LevyOkraj);
        Udalost.Okraj2 := @(Stanky[Stanek].PravyOkraj);
        PridejDoPrioritniFronty(Fronta, Udalost);
        Udalost.Jaka := U_ODSTRAN_STANEK;
        Udalost.YSouradnice := Stanky[Stanek].MaxY;
        PridejDoPrioritniFronty(Fronta,Udalost); {okraje jsou stejné ...}
    end;
end;

procedure ZpracujUdalost(Udalost : TUdalost; var Fronta : TPrioritniFronta;
                         var Intervaly : PIntervalovyAVLStrom); {zpracuje příslušnou událost z fronty}
var SousedL, SousedP : POkraj;
begin
    case Udalost.Jaka of
        U_PRIDEJ_STANEK : begin {nový stánek}
                SousedL := NejblizsiLevyOkraj(Intervaly, Udalost.Okraj1);
                    {koukneme se na levého souseda není-li také levým okrajem}
                if SousedL<>nil then if SousedL^.Levy then NalezenaKolize:=true; {jsme uvnitř stánku}
                if not NalezenaKolize then begin
                    PridejDoAVLStromu(Intervaly, Udalost.Okraj1);
                        {otestujeme, jestli není hrana mezi levou a pravou přidávanou}
                    SousedP := NejblizsiLevyOkraj(Intervaly, Udalost.Okraj2);
                    if SousedP<>Udalost.Okraj1 then
                        NalezenaKolize := true {nějaká hrana uvnitř => existuje překryv}
                    else begin
                        PridejDoAVLStromu(Intervaly, Udalost.Okraj2); {Přidání okrajů do stromu}
                        if length(Udalost.Okraj1^.Vrcholy)>2 then begin
                            {ještě přidáme, kde se bude levý okraj lámat, do fronty událostí}
                            Udalost.Jaka := U_VRCHOL_STANKU;
                            Udalost.YSouradnice := Udalost.Okraj1^.Vrcholy[1].Y;
                            PridejDoPrioritniFronty(Fronta, Udalost); {Okraj2 zůstává zachován}
                        end;
                        if length(Udalost.Okraj2^.Vrcholy)>2 then begin
                            Udalost.Jaka := U_VRCHOL_STANKU;
                            Udalost.YSouradnice := Udalost.Okraj2^.Vrcholy[1].Y;
                            Udalost.Okraj1 := Udalost.Okraj2;
                            PridejDoPrioritniFronty(Fronta, Udalost);
                        end;
                    end;
                end;
            end;
        U_VRCHOL_STANKU : begin {přesun na další vrchol stánku}
                OdeberZAVLStromu(Intervaly, Udalost.Okraj1);
                inc(Udalost.Okraj1^.AktualniPozice);
                if Udalost.Okraj1^.AktualniPozice < length(Udalost.Okraj1^.Vrcholy)-2 then begin
                        {pokud to není poslední úsek, zjistíme, kde bude další zlom}
                    Udalost.YSouradnice := Udalost.Okraj1^.Vrcholy[Udalost.Okraj1^.AktualniPozice+1].Y;
                    PridejDoPrioritniFronty(Fronta, Udalost); {vrátíme okraj zpět a otestujeme kolize}
                end;
                SousedL := NejblizsiLevyOkraj(Intervaly, Udalost.Okraj1);
                if Udalost.Okraj1^.Levy then begin {Test jestli nedošlo ke zkřížení v krajním bodu}
                    if SousedL<>nil then if SousedL^.Levy then NalezenaKolize:=true;
                end else begin
                    if SousedL = nil then NalezenaKolize:=true
                    else
                    if SousedL^.Mnohouhelnik <> Udalost.Okraj1^.Mnohouhelnik then NalezenaKolize:=true;
                end;
                PridejDoAVLStromu(Intervaly, Udalost.Okraj1); {a přidáme zpět}
            end;
        U_ODSTRAN_STANEK : begin {odebrereme oba okraje a jsme hotovi}
                OdeberZAVLStromu(Intervaly, Udalost.Okraj1);
                OdeberZAVLStromu(Intervaly, Udalost.Okraj2);
            end;
    end;
end;

begin
    Nacti;
    NajdiOkraje;
    Intervaly := nil;
    NalezenaKolize := false;
    Fronta.KorenHaldy := nil;
    Fronta.PosledniVrchol := nil; {zatím nejsou události}
    PridejOkrajeStanku(Fronta);
    repeat
        Udalost := Fronta.KorenHaldy^.Udalost;
        OdstranKorenPrioritniFronty(Fronta);
        ZpracujUdalost(Udalost, Fronta,Intervaly);
    until NalezenaKolize or (Fronta.KorenHaldy=nil);
    write('Kolize stánků ');
    if not NalezenaKolize then write('ne');
    writeln('byla nalezena.');
end.