Dotcpp  >  编程题库  >  蓝桥杯历届试题-邮局
题目 1457:

蓝桥杯历届试题-邮局

时间限制: 1s 内存限制: 128MB 提交: 927 解决: 177

题目描述

C村住着n户村民,由于交通闭塞,C村的村民只能通过信件与外界交流。为了方便村民们发信,C村打算在C村建设k个邮局,这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局,请从中选出k个来,使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。

输入格式

输入的第一行包含三个整数n,  m,  k,分别表示村民的户数、备选的邮局数和要建的邮局数。 
接下来n行,每行两个整数x,  y,依次表示每户村民家的坐标。 
接下来m行,每行包含两个整数x,  y,依次表示每个备选邮局的坐标。 
在输入中,村民和村民、村民和邮局、邮局和邮局的坐标可能相同,但你应把它们看成不同的村民或邮局。

数据规模和约定
对于100%的数据,1< =n< =50,1< =m< =25,1< =k< =10。

输出格式

输出一行,包含k个整数,从小到大依次表示你选择的备选邮局编号。(备选邮局按输入顺序由1到m编号)

样例输入

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

样例输出

2 4

提示

零基础的同学可以先学习基础,教程见:  C语言教程C++教程编译器教程数据结构教程Python教程单片机教程

视频教学见视频网课

标签