Värvide segamine

시간 제한1.2초메모리 제한1024 MB

요약
N개의 기계 색과 Q개의 질의 색이 3차원 RGB 공간에서 주어질 때, 맨해튼 거리로 가장 가까운 기계 색을 찾고 동률이면 번호가 작은 것을 출력한다.
난이도

어려움10점 중 8점

유형
분할 정복, 기하, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

Ehituspoes on masin, mis oskab punasest, rohelisest ja sinisest värvist (nimetame neid edaspidi põhivärvideks) segada kokku erinevaid värvitoone. Iga värvitoon, mida masin oskab kokku segada, on antud RGB-koodiga, mis näitab, kui palju mingit põhivärvi kulub. Kood on esitatud kolme 16-bitise arvuga. Ostjad soovivad saada mingeid spetsiifilisi värvitoone, mis on samuti antud oma RGB-koodidega. Masin aga ei pruugi osata teha täpselt nõutud tooni ning valib seetõttu lähima võimaliku vaste. "Lähedust" mõõdetakse 3D Manhattani kaugusega värviruumis. Näiteks värvitoonide "100 50 0" ja "20 25 10" vaheline kaugus on vastavate põhivärvide omavaheliste kauguste summa ehk ∣100−20∣+∣50−25∣+∣0−10∣=115|100-20|+|50-25|+|0-10|=115. Mõnel päeval on aga masinal mõni põhivärvidest (punane, roheline või sinine) hoopiski otsas. Sellisel juhul esitavad ostjad ka vaid selliseid soove, kus seda põhivärvi vaja ei ole. Masina konstrueerimisel on arvestatud, et võimalikud toonid oleksid värviruumis võimalikult ühtlaselt esindatud --- seetõttu võib eeldada, et võimalikud toonid on enam-vähem juhuslikud ja esindatud võrdse tõenäosusega. Kõik toonid, mida masin oskab teha, on omavahel erinevad, aga klientide soovid võivad kattuda.

입력

Tekstifaili esimesel real on värvitoonide arv 1≤N≤100,0001 \le N \le 100\\,000, mida masin oskab teha, ning soovide arv 1≤Q≤100,0001 \le Q \le 100\\,000, mida masinalt küsitakse. Järgmisel N+QN + Q real on igaühel 3 täisarvu lõigust 0…655350 \ldots 65535 ehk värvide RGB-koodid. Neist esimesel NN real on masinas segatavate värvitoonide koodid ja viimasel QQ real on ostjate soovitud värvide RGB-koodid.

출력

Tekstifaili väljastada QQ rida, igale reale üks täisarv: iga ostja soovitud värvi kohta sellele lähima värvi number, mida masin segada oskab. Masina segatavad värvid on nummerdatud 0…N−10 \ldots N-1 sisendis toodud järjekorras. Kui kaks värvi on samal kaugusel, väljastada väiksema numbriga värv.

예제3

  1. 예제 1

    입력
    3 3
200 0 0
8 0 0
100 0 0
8 0 0
300 0 0
150 0 0
    예상 출력
    1
0
0

  2. 예제 2

    입력
    3 3
75 25 0
100 100 0
150 50 0
100 50 0
50 100 0
200 30 0
    예상 출력
    0
1
2

  3. 예제 3

    입력
    4 3
5 5 5
200 200 200
150 10 10
0 0 255
0 0 0
10 10 200
175 105 105
    예상 출력
    0
3
1