z-rubberz
Na komadu daske zakucano je N razlicitih eksera, tako da nikoja tri nisu kolinearna. Na raspolaganju imate K gumica, koje se mogu rastezati do proizvoljne duzine. Prvi od datih eksera zvacemo centar. Centralni ekser ne pripada konveksnom omotacu datih eksera.
Treba postaviti date gumice oko eksera na sledeci nacin:
(1) svaka gumica obuhvata grupu eksera
(2) svi ekseri su u nekoj od gumica
(3) gumice se ne preklapaju, osim u centralnom ekseru
(4) gumice grade konveksne poligone, koji obuhvataju najmanje tri eksera
Za datu konfiguraciju eksera naci raspored gumica koji zadovoljava gornje uslove a da pritom minimizuje povrsinu koje one obuhvataju (za bolje objasnjenje videti sliku).
InputPodaci se ucitavaju sa standardnog ulaza. U prvom redu se nalaze brojevi K i N (2 <= K <= 50, 1 <= N <= 200), koji predstavlja broj gumica i broj eksera. U svakom od sledecih N redova nalaze se po dva cela broja X i Y iz opsega [-10.000, 10.000] koji predstavljaju pozicije eksera na dasci. Centralni ekser je predstavljen prvim ekserom u ovom nizu.
OutputNa standardnom izlazu, u jednoj liniji stampati najmanju mogucu povrsinu koju obuhvataju gumice pod gore navedenim uslovima. Rezultat stampati na dve decimale.
Ulaz:
Izlaz:
2 5
0 0
9 4
-8 8
-10 -2
4 -8Izlaz:
92.00Submit solution
Sign in to submit a solution.