Županijsko natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) - 2. zadatak

U malom se mjestu na obali prije tri godine pojavio prvi kriminalac.

1 Nažalost, institucije nisu ništa poduzele pa se tamo danas nalazi cijela skupina kriminalaca zbog kojih je život u tom malom gradiću potpuno stao, čak su otkazana i neka programerska natjecanja.

Nepoznati heroj odlučio je svemu stati na kraj.

Prvog je dana ulovio jednog kriminalca, običnu hulju, kako crta grafite po fasadi jedne stare crkve.

“Ajde mi objasni zašto si nacrtao ovih n točaka na zidu stare crkve. Prijavit ću te policiji!”, odrješito će heroj.

“Molim te nemoj me prijaviti, ja samo želim pokriti ovih n točaka proizvoljnim brojem konveksnih poligona s vrhovima u istaknutim točkama tako da suma površina tih poligona bude najmanja moguća”, odvrati mu hulja.

Heroj je odmah shvatio da se uopće ne radi o hulji, već o zalutalom mladom matematičaru.

Kao što i priliči jednom heroju, odlučio mu je pomoći sa zadatkom.

Najprije mu je objasnio kako je točke bolje prikazivati u koordinatnom sustavu, a ne na fasadama starih zdanja, a zatim je napisao program koji rješava ovaj problem.

Ulazni podaci

U prvom je retku prirodan broj n (3 ≤ n ≤ 20) iz teksta zadatka.

U i-tom od sljedećih n redaka su po dva prirodna broja xi i yi (0 ≤ |xi|, |yi| ≤ 109) koji predstavljaju koordinate i-te točke.

U testnim primjerima neće se pojaviti tri kolinearne točke.

Izlazni podaci

U prvi redak ispišite traženu najmanju sumu površina poligona.

Primjer zadatka

Ulaz

3
1 5
-3 4
2 -1

Izlaz

12.50000000

Ulaz

4
2 2
-2 2
2 -2
-2 -2

Izlaz

16.00000000

Ulaz

5
2 2
6 -1
5 7
5 4
4 2

Izlaz

3.50000000