Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Duomenų failas: rfid.in

Rezultatų failas: rfid.out

Jei norite pateikti savo sprendimą - prisijunkite.

RFID sekimas

Vytenis dirba didelės internetinės parduotuvės sandėlyje. Kai klientas pateikia užsakymą parduotuvei, šis yra perduodamas į sandėlį. Vytenis turi surasti visas užsakytas prekes, jas supakuoti ir išsiųsti klientui.

Sandėlyje galioja neįprasta tvarka: prekės nėra surikiuotos kokia nors tvarka, o išmėtytos atsitiktinai. Vytenis gali atlikti savo darbą, nes prekės yra sekamos RFID žymių pagalba. Kiekviena prekė patekusi į sandėlį gauna RFID žymę, o ant lubų išdėstyti sensoriai seka prekes.

Kiekvienas sensorius dirba r vienetų atstumu, t.y. jis gali nuskaityti RFID žymę, kuri yra ne toliau nei per r vienetų tiesia linija. Tačiau, jei atkarpa tarp sensoriaus ir prekės kerta ar liečia k sienų, sensoriaus darbo nuotolis sumažėja k vienetų ta kryptimi. Be to, sensoriai gali vienas kitam trukdyti, dėl to, atstumas tarp bet kurių dviejų sensorių yra bent r vienetų. Galite laikyti, kad nė vienas sensorius ar prekė yra padėti ant sienos.

Vytenis nori sužinoti, kiekvienai prekei, keli sensoriai gali nuskaityti jos žymę.

Pradiniai duomenys

Pirmoje eilutėje yra keturi sveikieji skaičiai atskirti tarpais: sensorių kiekis s (1\\les\\le250\\000), sensoriaus darbo nuotolis r (1\\ler\\le20), sienų kiekis w (1\\lew\\le10) ir prekių kiekis p (1\\lep\\le10\\000).

Tolesnėse s eilutėse yra po du sveikuosius skaičius x_i ir y_i (-10\\000\\lex_i,y_i\\le10\\000). Kiekviena tokia eilutė reiškia, kad yra sensorius su koordinatėmis (x_i,y_i). Atstumas tarp bet kurių dviejų sensorių yra nemažesnis už r.

Tolesnėse w eilutėse yra po keturis sveikuosius skaičius ax_i, ay_i, bx_i ir by_i (-10\\000\\leax_i,ay_i,bx_i,by_i\\le10\\000). Kiekviena tokia eilutė reiškia, kad yra tiesi siena tarp taškų (ax_i,ay_i) ir (bx_i,by_i). Šios atkarpos ilgis yra teigiamas.

Tolesnėse p eilutėse yra po du sveikuosius skaičius px_i ir py_i (-10\\000\\lepx_i,py_i\\le10\\000). Kiekviena tokia eilutė reiškia, kad yra prekė su koordinatėmis (px_i,py_i).

Rezultatai

Turi būti lygiai p eilučių, po vieną kiekvienai prekei. Šios eilutės turi būti pateiktos tokia pačia tvarka, kuria prekės yra pateiktos duomenyse.

Kiekvienos eilutės pradžioje turi būti sveikasis skaičius t, sensorių, kurie pasiekia prekę, kiekis. Toliau eilutėje turi t porų (x,y), sensorių, kurie pasiekia prekę, koordinatės. Jei yra keletas tokių sensorių, jie turi būti išrikuoti x koordinatės didėjimo tvarka. Jei yra keletas sensorių su ta pačia x koordinate, tokie sensoriai turi būti išrikiuoti y koordinatės didėjimo tvarka.

Pavyzdys

Duomenys Rezultatai 
4 3 4 7
0 0
-1 3
2 3
11 5
-4 -1 5 -1
3 4 6 1
11 4 11 3
12 5 12 8
1 1
0 -2
4 4
11 2
13 5
13 7
14 5
 
3 (-1,3) (0,0) (2,3)
1 (0,0)
0
0
1 (11,5)
0
0

Pavyzdžio iliustracija