$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\mod}{\,\mathrm{mod}\,} \newcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Priručnik za C++

Najkraća ograda

Autor zadatka
Saradnici
Autor rešenja zadatka
Izvor zadatka
vreme memorija ulaz izlaz
1 s 1000 Mb standardni ulaz standardni izlaz

U šumi postoji n vrsta stabala. Za svako od m stabala je data njegova vrsta i geografske koordinate. Šumar hoće da ogradi sva stabla jedne vrste žičanom ogradom pravougaonog oblika (gledano odozgo) čije ivice imaju pravac sever-jug i istok-zapad. Kakvu ogradu treba da napravi tako da potroši najmanje žice?

U prvom redu broj vrsta n i broj stabala m, razdvojeni razmakom. U svakom od sledećih m redova opis jednog stabla: x-koordinata, zatim y-koordinata, i na kraju indeks vrste, razdvojeni razmacima.

U prvom redu indeks ograđene vrste. U drugom redu četiri cela broja razdvojena razmacima koja predstavljaju koordinate temena ograde najmanjeg obima koja obuhvata sva stabla te vrste: najpre x i y koordinata donjeg levog temena, zatim x i y koordinata gornjeg desnog temena (I kvadrant). Ako ima više vrsta koje se mogu ograditi ogradom iste dužine, rešenje je ona sa najmanjim indeksom

1 ≤ n ≤ 500, 1 ≤ m ≤ 5000. Koordinate su celi brojevi u zatvorenom intervalu između 0 i 1000. Dva stabla mogu imati iste koordinate. Svaka vrsta mora biti zastupljena bar jednim stablom, dakle m ≥ n.

Ulaz Izlaz

2 5
3 1 0
5 2 0
4 2 1
0 4 0
6 0 1

1
4 0 6 2

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.