问题 25146 --PREV-24 邮局

25146: PREV-24 邮局

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

 C村住着n户村民,由于交通闭塞,C村的村民只能通过信件与外界交流。为了方便村民们发信,C村打算在C村建设k个邮局,这样每户村民可以去离自己家最近的邮局发信。

  现在给出了m个备选的邮局,请从中选出k个来,使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。

输入

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

数据规模和约定
  对于30%的数据,1<=n<=10,1<=m<=10,1<=k<=5;
  对于60%的数据,1<=m<=20;
  对于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

来源

 

[提交][状态]