题目描述
已知平面内 N 个点的坐标,求欧氏距离下的第 K 远点对。
两个点 P(x1,y1) 和 Q(x2,y2) 的欧氏距离定义为 d(P,Q)=(x1−x2)2+(y1−y2)2。
输入格式
输入文件第一行为用空格隔开的两个整数 N,K。
接下来 N 行,每行两个整数 X,Y,表示一个点的坐标。
输出格式
输出文件第一行为一个整数,表示第 K 远点对的距离的平方(一定是个整数)。
样例
10 5
0 0
0 1
1 0
1 1
2 0
2 1
1 2
0 2
3 0
3 1
9
数据范围与提示
Case # |
N |
1 |
2000 |
2 |
5000 |
3 |
10000 |
4 |
15000 |
5 |
20000 |
6 |
60000 |
7 |
70000 |
8 |
80000 |
9 |
90000 |
10 |
100000 |
对于所有测试点,1≤K≤100,K≤2N(N−1),0≤X,Y<231。