题目描述

C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。　　现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。 输入格式 　　输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。　　接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。　　接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。　　在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。 输出格式 　　输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号） 样例输入 5 4 20 02 03 13 31 10 11 02 13 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。

输入格式

输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。　　接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。　　接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。　　在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。 输出格式 　　输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号） 样例输入 5 4 20 02 03 13 31 10 11 02 13 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。

输出格式

输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号） 样例输入 5 4 20 02 03 13 31 10 11 02 13 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。

5 4 20 02 03 13 31 10 11 02 13 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。

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。

来源

蓝桥杯 历届试题