Van egy erdőnk és szeretnénk
körbekeríteni, tehát építsünk kerítést az erdő köré. Mivel szeretnénk a lehető
legkisebb költséggel építkezni, ezért határozzuk meg a lehető legrövidebb
kerítést, amelyen belül lesz az erdő minden fája.
Bemenet:
Az input.txt első sora
tartalmazza a tesztesetek számát, ezután következnek a tesztesetek. Egy
teszteset a következő szerkezetű. A teszteset első sora tartalmazza az erdő
fáinak a számát 2<n<10000, majd
n soron keresztül következnek az
egyes fák pozíciói, szóközzel vagy tabulátorral elválasztott két nem negatív
egészszám formájában. (A fák elhelyezkedését egy olyan síkon adjuk meg, ahol a
tengelyeket úgy határozzuk meg, hogy a fák pozíciója ne legyen negatív.) Az
egyszerűsítés érdekében tegyük fel, hogy a fák törzsének kiterjedése nulla és
az elhelyezkedésük egész koordinátájú pontokra esik. (A terület méretéhez képes
egy fa törzsének a kiterjedése elhanyagolható.)
Kimenet:
Minden tesztesetre adjuk meg a legrövidebb kerítés
hosszát.
(Nagy Tibor)