Անորոշ երկրպագուներ

Երաժշտական երկու ֆան-ակումբներ այգում նոր անդամներ են հավաքագրում։ Հայտնի է, թե որտեղ են կանգնած գոյություն ունեցող որոշ երկրպագուներ և որ ակումբին են նրանք սատարում. նրանցից յուրաքանչյուրի դիրքը երկչափ քարտեզի վրա կետ է՝ համապատասխան ակումբի անունով։ Երբ նոր մարդ է գալիս և կանգնում որևէ տեղում, նա որոշում է կայացնում՝ հիմնվելով իրեն ամենամոտ գտնվող երկու երկրպագուների ընտրության վրա։ Եթե այդ երկու ամենամոտ երկրպագուները տարբեր ակումբների են պատկանում, արդյունքը համարվում է ոչ-ոքի։

Մուտքի առաջին տողում տրված է մեկ բառ metric՝ որը կարող է լինել կա՛մ L2՝ ուղիղ գծով (էվկլիդյան) հեռավորության, կա՛մ L1՝ Մանհեթենյան հեռավորության համար։ Երկրորդ տողում տրված է ամբողջ թիվ n՝ հայտնի երկրպագուների թիվը ներկայացնելու համար։ Հաջորդ n տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y՝ որոնց հաջորդում է ակումբի անունը (մեկ բառ)՝ նկարագրելով մեկ երկրպագուի դիրքն ու ակումբը։ Հաջորդ տողում տրված է ամբողջ թիվ q՝ ստուգման ենթակա դիրքերի քանակը ներկայացնելու համար։ Վերջին q տողերից յուրաքանչյուրը պարունակում է երկու իրական թիվ x y նոր մարդու դիրքի համար։

Յուրաքանչյուր դիրքի համար հաշվեք հեռավորությունները մինչև բոլոր հայտնի երկրպագուները՝ օգտագործելով նշված մետրիկը, վերցրեք երկու ամենամոտ երկրպագուներին (k=2) և տպեք հաղթող ակումբի անունը, եթե երկուսն էլ պատկանում են նույն ակումբին, հակառակ դեպքում՝ տպեք tie։ Եթե հարևանների ընտրության ժամանակ հեռավորությունները լրիվ հավասար են, ապա մուտքային տվյալներում ավելի վաղ նշված տողերն ընդունեք որպես ավելի մոտ գտնվողներ։