题目
2020 年 6 月 8 日，国务院联防联控机制发布《关于加快推进新冠病毒核酸检测的实施意见》，提出对“密切接触者”等八类重点人群“应检尽检”，其他人群“愿检尽检”。
某市设有$n$个核酸检测点，编号从$1$到$n$，其中$i$号检测点的位置可以表示为一个平面整数坐标$(x_i, y_i)$。
为方便预约核酸检测，请根据市民所在位置$(X, Y)$，查询距其最近的三个检测点。
多个检测点距离相同时，编号较小的视为更近。
输入
输入共$n+1$行。
第一行包含用空格分隔的三个整数$n、X$和$Y$，表示检测点总数和市民所在位置。
第二行到第$n+1$行依次输入$n$个检测点的坐标。第$i+1$行$（1≤i≤n）$包含用空格分隔的两个整数$x_i$和$y_i$，表示$i$号检测点所在位置。
输出
输出共三行，按距离从近到远，依次输出距离该市民最近的三个检测点编号。
输入样例1
输出样例1
输入样例2
1
2
3
4
5
6
| 5 0 1
-1 0
0 0
1 0
0 2
-1 2
|
输出样例2
样例2解释：
![]()
解答（Dev-CPP环境）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point{
int id;
int dis;
Point(int id,int dis){
this->id=id;
this->dis=dis;
}
};
int calc(int X,int Y,int x,int y){
return (X-x)*(X-x)+(Y-y)*(Y-y);
}
bool cmp(Point p1,Point p2){
if(p1.dis==p2.dis){
return p1.id<p2.id;
}
return p1.dis<p2.dis;
}
int main(){
int n,X,Y,px,py,d;
vector<Point> points;
cin>>n>>X>>Y;
for(int i=0;i<n;i++){
cin>>px>>py;
d=calc(X,Y,px,py);
points.push_back(Point(i+1,d));
}
sort(points.begin(),points.end(),cmp);
for(int i=0;i<3;i++){
cout<<points[i].id<<endl;
}
return 0;
}
|
