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

Վստահության չափիչ

Երաժշտական հավելվածը օգտատերերին դասավորում է ճաշակի երկչափ քարտեզի վրա։ Հավելվածին արդեն հայտնի են մի քանի օգտատերեր և նրանց նախասիրությունները՝ հավանել են երգը (1) կամ ոչ (0)։ Նոր օգտատիրոջ դիրքի համար հավելվածը գտնում է k ամենամոտ հայտնի օգտատերերին՝ օգտագործելով ուղիղ գծով հեռավորությունը (Էվկլիդյան L2)։ Այնուհետև, որպես վստահության աստիճան, հավելվածը հաշվում է, թե այդ k հարևանների քանի տոկոսն ունի պիտակ 1։

Ձեր խնդիրն է իրականացնել այդ հնարավորությունը հավելվածի համար։

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

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

Հաջորդ տողում տրված է k ամբողջ թիվը (1 ≤ k ≤ n)։

Այնուհետև տրված է q ամբողջ թիվը՝ ստուգվելիք նոր օգտատերերի դիրքերի քանակը։

Վերջին q տողերից յուրաչափյուրը պարունակում է երկու իրական թիվ x y ներկայացնում են նոր օգտատերերի կոորդինատները։

Ծրագիրը պետք է ելքում տպի q տող։ Յուրաքանչյուր տող պետք է պարունակի 1-երի տոկոսային քանակը՝ համապատասխան նոր օգտատիրոջ համար։

Մուտք

Ելք

5
0 0 1
2 0 0
0 2 1
2 2 0
1 1 1
3
0.9 0.9
1.1 1.1
2 1

66.66666666666667
33.333333333333336
33.333333333333336

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

75
75

4
0 0 0
0 1 0
1 0 0
3 3 1
4
2
0.2 0.2
3 3

25
25

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