蓝桥杯-历届试题 邮局

问题描述

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

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

输入格式

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

输出格式

输出一行,包含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

数据规模和约定

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

参考代码

此处为隐藏的内容!
发表评论并刷新,才能查看
俊霖

发表评论

您必须

目前评论:14   其中:访客  13   博主  1

  1. 茹雪 5

    谢谢啦,辛苦啦。感谢感谢!

  2. wangsqhhu 1

    看看

  3. Snail 1

    非常有用,认真学习!

  4. 虐己虐亲 1

    有用

  5. ymx200181 5

    有用

  6. 努力、做自己℡ 1

    看66666666666

  7. KingLime 0

    看看666666666666666666666666666

  8. abab99 2

    666666666666666666666666看一下

  9. 倒e朵* 2

    dfs剪枝

  10. 梦醒 4

    666膜拜大神

  11. qwer66666626 0

    求正解

  12. jiangqian 2

    文章很有用~

  13. 背影 0

    谢谢博主