Մեքենայական ուսուցում

Ամենամոտ հղումները

Թանգարանի համադրողը հարթ տախտակի վրա տեղորոշում է հայտնի հղումները։ Երբ նոր արվեստի գործ է ժամանում, համադրողը ցանկանում է կազմել դրան ամենամոտ գտնվող հղումների ցանկը։

Ձեր խնդիրն է յուրաքանչյուր արվեստի գործի համար գտնել k ամենամոտ հղումների ինդեքսները՝ օգտագործելով ուղիղ գծով հեռավորությունը։

Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ տախտակի վրա առկա հղումների քանակը։

Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x և y, որոնք նկարագրում են հղումներից մեկի դիրքը։ Հղումները համարակալվում են 1-ից՝ ըստ իրենց հերթականության։

Հաջորդ տողում տրված է k ամբողջ թիվը, թե քանի հարևան պետք է գտնել յուրաքանչյուր արվեստի գործի համար։

Հաջորդ տողում տրված է q ամբողջ թիվը՝ ստուգվող արվեստի գործերի քանակը։

Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ՝ x և y, որոնք նկարագրում են արվեստի գործի դիրքը։

Յուրաքանչյուր արվեստի գործի համար պետք է տպել k ամենամոտ հղումների ինդեքսները՝ բաժանված բացատանիշով։ Ինդեքսները պետք է դասավորված լինեն ըստ Էվկլիդյան (L2) հեռավորության աճման կարգի։ Եթե մի քանի հղումներ ունեն նույն հեռավորությունը, ապա առաջինը պետք է տպել ավելի փոքր ինդեքս ունեցողը։

Մուտք

Ելք

4
0 0
2 0
0 2
2 2
2
3
0.9 0.1
1.1 0
1 1

1 2
2 1
1 2

4
-1 0
3 0
0 4
2 4
3
2
2 1
2 5

2 4 1
4 3 2

3
0 0
0 2
0 -2
2
1
0 1

1 2

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue