#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。