Դասակարգում ըստ հեռավորության քառակուսու

Թանգարանը խնդրում է ձեզ դասակարգել նկարները՝ ըստ իրենց ոճի՝ պարզ 2D հատկանիշների քարտեզի վրա։ Ձեր հաշվիչի քառակուսի արմատի ստեղնը փչացել է, ուստի դուք պետք է դասակարգեք հարևաններին՝ օգտագործելով միայն Էվկլիդյան հեռավորության քառակուսին՝ ։

Յուրաքանչյուր նոր նկարի համար գտեք k ամենամոտ հայտնի նկարները՝ դասավորելով դրանք ըստ -ի աճման կարգի (առանց քառակուսի արմատի)։ Եթե երկու կամ ավելի հայտնի նկարներ ունեն ճիշտ նույն հեռավորությունը, նախապատվությունը տվեք այն նկարին, որը մուտքային տվյալներում ավելի շուտ է հանդիպում։

Կանխատեսեք ոճը՝ հիմնվելով այդ k հարևանների մեջ ամենահաճախ հանդիպող ոճի վրա (majority vote)։ Եթե ձայները հավասար են բաշխվել, ընտրեք այն ոճը, որը պատկանում է մուտքային տվյալներում ավելի շուտ հանդիպող նկարին (հավասար ձայներ հավաքածների միջից)։

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

Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y, որոնց հաջորդում է ոճը նշող բառ, օրինակ՝ modern կամ classic։ Այս տվյալները նկարագրում են մեկ նկարի դիրքն ու ոճը։

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

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

Յուրաքանչյուր հարցման համար ծրագիրը պետք է տպի մեկ տող․ սկզբում՝ կանխատեսված ոճը, այնուհետև՝ օգտագործված k հարևանների հեռավորությունների քառակուսիները՝ դասավորված ըստ հարևանների հերթականության։