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

KNN Regression․ Քանի՞ աստղ

Մի փոքր սթրիմինգային հավելված ցանկանում է արագ գուշակել նոր ֆիլմի վարկանիշը։ Պատկերացրեք, որ բոլոր հայտնի ֆիլմերը տեղադրված են պարզ երկչափ քարտեզի վրա, որտեղ միմյանց ավելի մոտ գտնվող ֆիլմերն ավելի նման են։ Նոր ֆիլմի վարկանիշը (աստղերի քանակը) կանխատեսելու համար կարելի է դիտարկել այդ քարտեզի վրա գտնվող k ամենամոտ հայտնի ֆիլմերը (ըստ ուղիղ գծով հեռավորության), հաշվել դրանց վարկանիշների միջինը և օգտագործել ստացված թիվը։

Եթե հարևաններին դասակարգելիս մի քանի ֆիլմեր գտնվում են նույն հեռավորության վրա, ապա առավելությունը տրվում է այն ֆիլմին, որը մուտքային տվյալներում ավելի շուտ է հանդիպում։

Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ հայտնի ֆիլմերի քանակը։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու լողացող կետով թիվ x y և դրանց հաջորդող լողացող կետով թիվ r։ Դրանք համապատասխանաբար նկարագրում են ֆիլմի դիրքը և դրա վարկանիշը։

Հաջորդ տողում տրված է k ամբողջ թիվը։

Հաջորդ տողում տրված է q ամբողջ թիվը՝ այն նոր ֆիլմերի քանակը, որոնց վարկանիշը պետք է գնահատել։ Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու լողացող կետով թիվ x y՝ նոր ֆիլմի դիրքը։

Յուրաքանչյուր նոր ֆիլմի համար տպեք կանխատեսված վարկանիշը։

Մուտք

Ելք

4
0 0 4.0
2 0 2.0
0 2 5.0
3 3 1.0
3
2
0.9 0.1
1 1

3.6666666666666665
3.6666666666666665

3
-1 0 4.5
3 0 2.0
0 4 3.0
2
2
2 1
2 5

3.25
2.5

3
0 0 4.0
0 2 2.0
2 0 5.0
1
3
0 1
0 1.001
1 1

4
2
4

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