2537: KNN算法

KNN算法，也叫k-近邻算法，是机器学习中的基础算法，其工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集合中每一个数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是一个不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

在本题中，我们要求利用电影的打斗镜头和接吻镜头的数量m和n判定电影的类型，两个电影的距离可以用欧式距离公式表示

distance = sqrt((m1-m2)^2+(n1-n2)^2)，k取3

输入第一行为正整数N（N<100），表示样本数据的数量。

接下来N行样本数据，每一个样本数据包括3个正整数a，b，c，其中a表示打斗镜头数量，b表示接吻镜头数量，c表示电影类型（1表示爱情片，2表示动作片）。

最后一行包括两个正整数a和b，表示未知电影类型的打斗镜头数量和接吻镜头数量。