跳至正文
题库4126
#4126

邮局

查看题目操作

邮局

题目描述

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

输入格式

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

输出格式

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

样例

10 5 3
67 41
0 34
24 69
58 78
64 62
45 5
27 81
91 61
42 95
36 27
4 91
53 2
82 92
16 21
95 18
1 3 4 

说明/提示

对于30%的数据,1<=n<=10,1<=m<=10,1<=k<=5;  对于60%的数据,1<=m<=20;  对于100%的数据,1<=n<=50,1<=m<=25,1<=k<=10。 配图

来源

蓝桥杯 历届试题