Problem1619--找礼物 find [3*]

1619: 找礼物 find [3*]

Time Limit: 1.000 Sec  Memory Limit: 128 MB
Submit: 7  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

【问题描述】新年到了,突然间,就在那美丽的一霎那,你好友和你(K个 人)的周围满是礼物,你发扬你帅气的风格,让你的好友先拿,但是每个人只能拿当前离自己最近的礼物[当然如果有并列的多个礼物离你的距离相等(精确到小数 后四位,所有运算均为去尾),这些礼物就都属于这个人]。现在你们所在的位置是原点(0,0),每个礼物的位置用坐标表示。现在告诉你每个礼物的坐标,还 有每个礼物是谁送的。要你找出你的礼物离你多远,你能拿到多少礼物,这些礼物是谁送的。如果你拿不到礼物,请输出“555…”
【输入】第一行:N 和 K 分别表示礼物的个数和人数。
第二到N+1行:每行先是赠送礼品人的姓名,然后是礼物的坐标(x,y)。
数据间空格分割
【输出】
第一行: D 和 U 表示礼物距你多远(只要去尾后的整数)和你能拿到多少礼物。
第二到U+1行:每行一个人名,表示送礼的人。<按照输入的顺序输出>
【输入输出样例】
样例1:输入(find.in):
5 2
Jason 1 1
Herry 4 4
Patty 3 4
Tom 2 10
Petter 5 10
输出(find.out):
5 1
Patty

样例2:输入(find.in):
6 2
Jim 1 ?1
Flord 3 ?3
Joseph ?1 1
Steve 3 3
Tiger 2 ?10
User 10 20
输出(find.out):
4 2
Flord
Steve
样例二说明:jim 和 joseph 的礼品是等距的距离最短,被第一个人拿走,剩下的四个人中flord和steve的礼物也是等距的计算得到距离为4。
【数据范围】
对于30%的数据 K≤N≤1000 对于所有的数据 K≤N≤100000 所有的坐标绝对值小于10^6

Source/Category


[Submit] [Status]