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

Որքան մոտ է կարծիքը, այնքան մեծ է դրա կշիռը

Դուք ունեք օգտատերերի կարծիքների քարտեզ, որտեղ յուրաքանչյուր կարծիք ունի իր տեղադիրքն ու գնահատականը։ Երբ ցանկանում եք որևէ նոր կետի համար գնահատական հաշվել, մոտակա կարծիքներն ավելի մեծ ազդեցություն պետք է ունենան, քան հեռավորները։ Օգտագործեք k ամենամոտ հայտնի կարծիքները, որոնցից յուրաքանչյուրի կշիռը հաշվեք w = 1/d բանաձևով, որտեղ d-ն ուղիղ գծով (Էվկլիդյան, L2) հեռավորությունն է մինչև փնտրվող կետը։ Եթե հայտնի կարծիքներից որևէ մեկը գտնվում է ճիշտ փնտրվող կետում (d = 0), ապա անտեսեք մնացած բոլոր կարծիքները և որպես պատասխան վերադարձրեք այդ կետում գտնվող կարծիքների գնահատականների միջին թվաբանականը։

Մուտքի առաջին տողում տրված է n ամբողջ թիվը՝ հայտնի կարծիքների քանակը։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y, որոնց հաջորդում է s իրական թիվը։ Այս թվերը նկարագրում են կարծիքի դիրքն ու գնահատականը։

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

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

Ծրագիրը պետք է տպի կանխատեսված գնահատականները։

Մուտք

Ելք

3
0 0 4
2 0 2
0 2 5
2
2
1 0
0.5 1.5

3
4.690983005625052

4
0 0 2
1 1 3
1 1 4
2 2 5
3
2
1 1
1.1 1.1

3.5
3.5789473684210527

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

3.5
4.414213562373095
3.447818343361264

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