Distance
Time Limit : 10 Second
Memory Limit : 256 MB
Submission: 58
Solved: 4
- Description
- The furthest distance in the world is not between life and death
But when i stand in front of you ,
Yet you don't know that I love you
The furthest distance in the world is not when i stand in front of you,
Yet you can't see my love
But when undoubtedly knowing the love from both,
Yet cannot be together
The furthest distance in the world is not being apart while being in love
But when plainly can not resist the yearning,
Yet pretending you have never been in my heart
The furthest distance in the world is not when plainly can not resist the yearning,
yet pretending you have never been in my heart
But using one's indifferent heart
to dig an uncrossable river for the one who loves you
Tagore——Stray Birds
As a status shared by ACMer on RenRen says: It’s a signal to be love, when a girl becomes an ACMer. It’s a signal to be lonely, when a boy becomes an ACMer. Taney, The leader of CUG ACM team, is anxious about this problem for the team members. He wants to help every male member to find a girlfriend.
To finish this important and hard task, he designs a metric, to measure the personality differences between boys and girls. According to Taney’s theory, the personality differences between lovers should not be too much or too less. Too much means the two one are not live together well, and too less means the two one are too similarly to find funny to live together. The personality differences are measured by a distance. Everyone has a vector (A, B, C) to describe his personality. And the distance between a boy and a girl is the Euclidean distance:
There are N girls in Taney’s girl Database, give you a boy’s personality please find out the Kth closest girl to him.
- Input
- The first line of the input gives the number of test cases, T(T≦10). The first line of each case contains two integers, N and M(N, M≦20000). N is the number of girls, M is the number of boys. N+M lines follow, the first N lines gives out the personality vector of the N girls, and the last M lines，we first give out the K(K≦100), which means he want find the Kth closest girl, then the personality vector of the M boys, for each boy.
- Output
- For each boy output the distance between him and the Kth closest girl. Round the numbers in the output to 6 digits after decimal point.
- sample input
-
1 5 5 4.5 1.0 9.5 3.0 7.0 5.0 0.0 8.0 0.5 6.0 0.0 9.5 5.5 3.0 7.5 3 2.0 0.0 7.0 3 4.0 0.5 6.0 3 8.0 3.0 6.5 3 4.5 6.5 8.0 3 1.5 7.0 0.0
- sample output
-
4.716991 4.062019 5.024938 5.700877 9.394147
- hint
- source
- 中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛