Time Limit: 10 second
Memory Limit: 2 MB
问题描述
新年到了，突然间，就在那美丽的一霎那，你好友和你（K个人）的周围满是礼物，你发扬你帅气的风格，让你的好友先拿，但是每个人只能拿当前离自己最近的礼物[当然如果有并列的多个礼物离你的距离相等（精确到小数后四位,所有运算均为去尾），这些礼物就都属于这个人]。现在你们所在的位置是原点(0,0)，每个礼物的位置用坐标表示。现在告诉你每个礼物的坐标，还有每个礼物是谁送的。要你找出你的礼物离你多远，你能拿到多少礼物，这些礼物是谁送的。如果你拿不到礼物，请输出“555…”
Input
第一行：N 和 K 分别表示礼物的个数和人数。
第二到N+1行：每行先是赠送礼品人的姓名，然后是礼物的坐标（x,y）。
数据间空格分割
Output
第一行： D 和 U 表示礼物距你多远（只要去尾后的整数）和你能拿到多少礼物。
第二到U+1行：每行一个人名，表示送礼的人。<按照输入的顺序输出>
Sample Input
10 2 Pos 18426 3429 Kill -28989 -12602 WGPO -6095 11806 EhiEN 4 -3 DICV 7752 -27723 FBI 15713 -24074 QOHR -3194 -30639 WWJ 3 4 GKIX -5 0 CB 0 2
Sample Output
5 3 EhiEN WWJ GKIX
【题解】
保留4位的方法是 floor( sqrt(x*x + y*y) * 10000)/10000；存入数组中，以距离为关键字进行升序排。然后先给其他的小伙伴分，最后剩下自己的，在输入数据的时候记录每个礼物出现的先后顺序，最后输出的时候对自己要输出的礼物按照出现的顺序再排一次序。最后输出就好。这里的double类可以直接用“==”判断两个数是否相等。前面输入字符串的时候，用了char* name[90000] 这个东西，在输入之前要getchar一下，然后是num[i] = new char[1000],之后就能用scanf("%s")来进行输入了，会遇到空格停止。所以可以直接一排输入scanf("%s%lf%lf")，当然这是从别人那里挖过来的。用cin会超时。
【代码】
#include <cstdio>
#include <iostream>
#include <string>
#include <cmath>
#include <stdlib.h>
using namespace std;
struct data
{
double dis;
int first;
};
int n,k;
data a[90000];
char* name[90000]; //要记住这个输入字符串的写法
void input_data()
{
scanf("%d %d",&n,&k);
int m = 0;
getchar(); //在用之前要先getchar一下。
for (int i = 1;i <= n;i++)
{
name[i] = new char[1000]; //记住 new char [长度]
double x,y;
scanf("%s%lf%lf",name[i],&x,&y); //就可以直接用“%s"来进行输入了
a[i].dis = floor( sqrt(x*x + y*y) * 10000)/10000; //floor是取整函数
a[i].first = ++m; //记录下每个礼物出现的先后顺序
}
}
void kp(int l,int r) //以距离为关键字进行从小到大排
{
int i = l,j = r;
double m = a[(i+j)/2].dis;
do
{
while (a[i].dis < m) i++;
while (m < a[j].dis) j--;
if (i <= j)
{
a[0] = a[i];a[i] = a[j];a[j] = a[0]; //与之相关的所有东西 都要进行变换
name[0] = name[i];name[i] = name[j];name[j] = name[0];
i++;j--;
}
}
while (i <= j);
if (l < j) kp(l,j);
if (i < r) kp(i,r);
}
void kp2(int l,int r) //以出现的先后顺序为关键字 进行从小到大排序
{
int i = l,j = r,m = a[(i+j)/2].first;
do
{
while (a[i].first < m) i++;
while (m < a[j].first) j--;
if (i <= j)
{
a[0] = a[i];a[i] = a[j];a[j] =a[0];
name[0] = name[i];name[i] = name[j];name[j] = name[0];
i++;j--;
}
}
while (i <=j );
if (l < j) kp2(l,j);
if (i < r) kp2(i,r);
}
void get_ans()
{
k--; //k包括自己 我们先减去自己 处理其他人
kp(1,n);
int i = 1;
while (k > 0 && i <= n) //先过滤掉别人的礼物
{
int j = i+1;
while ( a[j].dis == a[i].dis) j++;
i = j;
k--;
}
if (k > 0) //如果别人都没分完则自己不可能有剩余礼物。但是好像有问题。。。如果别人刚好分完了呢？我在下面加几行。
{
printf("555…");
return;
}
if (k == 0 && i > n)
{
printf("555…");
return;
}
int j = i+1;
while ( a[j].dis == a[i].dis) j++;//然后找哪些礼物是自己的。
int dd = int(a[i].dis); //直接取整就好
printf("%d %d
",dd,j-i);
kp2(i,j-1); //对自己的礼物以出现的先后顺序进行排序。
for (int kk = i;kk <=j-1;kk++)
printf("%s
",name[kk]);
}
int main()
{
//freopen("F:\rush.txt","r",stdin);
input_data();
get_ans();
return 0;
}