DRŽAVNO NATJECANJE 2013 – Prvi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 2. zadatak

Goran se upravo uključio u dobrovoljno vatrogasno društvo i već je dobio prvi zadatak!

Njegove algoritamske vještine nadaleko su poznate, pa je zamoljen da odredi lokacije za K budućih vatrogasnih domova kako bi sve kuće u selu bile što bolje zaštićene u slučaju požara.

Svaki od K domova smjestit će se u jednoj od postojećih kuća.

Kuće su označene prirodnim brojevima od 1 do N^1 (prema redoslijedu u ulaznim podacima) te su za svaku kuću A poznate njene koordinate - dva cijela broja, XA i YA.

Goran vas je upravo nazvao i moli vas za pomoć, jer je otišao na put, a zaboravio ponijeti svoj laptop.

Preko telefona ste dobili sljedeće objašnjenje algoritma koji Goran želi iskoristiti za odabir domova:

1. U prvom koraku, za privremena mjesta K vatrogasnih domova odabiru se lokacije prvih K kuća redom prema oznakama. Za privremenu lokaciju prvog vatrogasnog doma odabrat će se lokacija prve kuće, za lokaciju drugog vatrogasnog doma lokacija druge kuće itd.

2. Nakon toga je potrebno svaku kuću “pridružiti” njoj najbližem vatrogasnom domu. Udaljenost definiramo kao zbroj apsolutnih vrijednosti razlika koordinata (udaljenost kuće A i kuće B je |XA-XB|+|YA-YB|). Ukoliko postoji više domova s najmanjom udaljenosti, kuća se pridružuje domu s najmanjom oznakom. Kažemo da sve kuće pridružene i-tom vatrogasnom domu čine i-tu vatrogasnu grupu.

3. Za svaku vatrogasnu grupu, pronalazi se novaprivremena pozicijanjenog vatrogasnog doma tako da se odabere ona kuća unutar grupe toga doma čiji je ukupni zbroj udaljenosti do svih ostalih kuća unutar promatrane vatrogasne grupe najmanji. Ponovo, u slučaju izjednačenja ukupnih udaljenosti, potrebno je birati kuću s najmanjom oznakom.

4. Ako se u koraku 3 pozicija vatrogasnog doma u barem jednoj od grupa promijenila, onda postupak ponavljamo tj. idemo na korak 2. U suprotnom, algoritam završava te pozicije vatrogasnih domova u tom trenutku postaju konačne.

Ovaj postupak ima svojstvo da sigurno završava i to nakon malog broja iteracija.

Napiši program koji za zadane lokacije kuća u selu te traženi broj vatrogasnih domova K pronalazi konačne pozicije vatrogasnih domova koje Goranov algoritam određuje.

Test podaci će biti takvi da će Goranov algoritam za njih završavati nakon najviše 30 iteracija (jedna iteracija se sastoji od drugog, trećeg i četvrtog koraka).

Ulazni podaci

U prvom retku ulaza nalaze se prirodni brojevi N i K (1 ≤ K ≤ N ≤ 100), broj kuća u Goranovom selu i broj vatrogasnih domova čije je lokacije potrebno odrediti.

U svakom od sljedećih N redaka nalazi se po jedan par cijelih brojeva XA, YA (1 ≤ XA, YA ≤ 1000), koordinate A-te kuće.

Niti jedan par kuća neće se nalaziti na istim koordinatama.

Izlazni podaci

Potrebno je ispisati K redova. U A-ti red potrebno je ispisati par brojeva XA, YA odvojenih razmakom – koordinate konačne pozicije A-tog vatrogasnog doma.

Primjeri test podataka

Ulaz

4 2
4 5
9 8
4 2
10 7

Izlaz

4 5
9 8

Ulaz

9 3
8 4
10 2
8 10
5 6
1 5
6 5
7 5
7 9
10 4

Izlaz

6 5
10 2
8 10