Najkraća ograda
| vreme | memorija | ulaz | izlaz |
|---|---|---|---|
| 1 s | 1000 Mb | standardni izlaz | standardni ulaz |
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.
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.