1449: [蓝桥杯]邮局

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:47 通过:9

题目描述

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

输入格式

输入的第一行包含三个整数n, m, k,分别表示村民的户数、备选的邮局数和要建的邮局数。

接下来n行,每行两个整数x, y,依次表示每户村民家的坐标。

接下来m行,每行包含两个整数x, y,依次表示每个备选邮局的坐标。

在输入中,村民和村民、村民和邮局、邮局和邮局的坐标可能相同,但你应把它们看成不同的村民或邮局。

1<=n<=50,1<=m<=251<=k<=10

输出格式

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

输入样例 复制

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

输出样例 复制

2 4