program KralPotvornik; const Presnost = 1E-10; {U reálných čísel musíme počítat s chybou} type PSloup = ^TSloup; TSloup = record X,Y:real; Dalsi:PSloup; end; var Sloupy:PSloup; function Nacti:PSloup; var NovySloup:PSloup; Vystup:PSloup; PocetSloupu:longint; begin Vystup:=nil; Readln(PocetSloupu); if PocetSloupu<3 then begin writeln('A z tohohle chces vytvorit konvexni obal?!'); halt; end; while PocetSloupu>0 do begin new(NovySloup); readln(NovySloup^.X,NovySloup^.Y); NovySloup^.Dalsi:=Vystup; {Přidáme do seznamu sloupů} Vystup:=NovySloup; dec(PocetSloupu); end; Nacti:=Vystup; end; procedure MergeSort(var Co:PSloup); var Seznam:array[boolean] of PSloup; DalsiPrvek,PosledniPrvek:PSloup; KterySeznam:boolean; begin if Co^.Dalsi=nil then exit; {Není co řešit} KterySeznam:=false; Seznam[false]:=nil;Seznam[true]:=nil; while Co<>nil do begin DalsiPrvek:=Co^.Dalsi; Co^.Dalsi:=Seznam[KterySeznam]; Seznam[KterySeznam]:=Co; KterySeznam:=not(KterySeznam); Co:=DalsiPrvek; end; MergeSort(Seznam[false]); MergeSort(Seznam[true]); PosledniPrvek:=nil; while (Seznam[false]<>nil) and (Seznam[true]<>nil) do begin KterySeznam:=Seznam[true]^.XSeznam[false]^.Y; {X stejné, rozhoduje Y} DalsiPrvek:=Seznam[KterySeznam]; Seznam[KterySeznam]:=Seznam[KterySeznam]^.Dalsi; if PosledniPrvek=nil then Co:=DalsiPrvek {Výstup je zatím prázdný} else PosledniPrvek^.Dalsi:=DalsiPrvek; {Přidáme na konec} DalsiPrvek^.Dalsi:=nil; {Opravíme konec} PosledniPrvek:=DalsiPrvek; end; PosledniPrvek^.Dalsi:=Seznam[Seznam[false]=nil]; end; {...a je to setříděné} procedure PridejKopii(Sloupy:PSloup); var Kopie,Nova:PSloup; begin Kopie:=nil; while Sloupy^.Dalsi<>nil do begin new(Nova); Nova^:=Sloupy^; Nova^.Dalsi:=Kopie; Kopie:=Nova; Sloupy:=Sloupy^.Dalsi; end; Sloupy^.Dalsi:=Kopie; {...a přidáme kopii na konec} end; function KonvexniObal(ZCeho:PSloup):PSloup; var Obal,DalsiSloup:PSloup; Vektor1,Vektor2:record X,Y:real; end; begin DalsiSloup:=ZCeho; ZCeho:=ZCeho^.Dalsi; DalsiSloup^.Dalsi:=nil; Obal:=ZCeho; ZCeho:=ZCeho^.Dalsi; Obal^.Dalsi:=DalsiSloup; {Vložíme první 2 body do posloupnosti} while ZCeho<>nil do begin DalsiSloup:=ZCeho; ZCeho:=ZCeho^.Dalsi; DalsiSloup^.Dalsi:=Obal; Obal:=DalsiSloup; while Obal^.Dalsi^.Dalsi<>nil do begin {Máme alespoň 3 body?} Vektor1.X:=Obal^.Dalsi^.X-Obal^.Dalsi^.Dalsi^.X; Vektor1.Y:=Obal^.Dalsi^.Y-Obal^.Dalsi^.Dalsi^.Y; Vektor2.X:=Obal^.X-Obal^.Dalsi^.X; {Vektor2 určuje směr predposl. a posl. sloupu} Vektor2.Y:=Obal^.Y-Obal^.Dalsi^.Y; {Vektor1 je totéž vzhledem k předchozím dvěma} if (Vektor1.X*Vektor2.Y-Vektor1.Y*Vektor2.X)>Presnost then break; DalsiSloup:=Obal^.Dalsi; {Bod je třeba odebrat} Obal^.Dalsi:=Obal^.Dalsi^.Dalsi; dispose(DalsiSloup); end; end; KonvexniObal:=Obal; end; function Delka(Obal:PSloup):real; var Vystup:real; begin Vystup:=0; while Obal^.Dalsi<>nil do begin Vystup:=Vystup+sqrt(sqr(Obal^.X-Obal^.Dalsi^.X)+sqr(Obal^.Y-Obal^.Dalsi^.Y)); Obal:=Obal^.Dalsi; end; Delka:=Vystup; end; begin Sloupy:=Nacti; MergeSort(Sloupy); PridejKopii(Sloupy); Sloupy:=KonvexniObal(Sloupy); writeln('Delka plotu je:',Delka(Sloupy):10:3); end.