称检测点查询 202009-1 【CSP】

男娘i 2023-09-26 16:57 24阅读 0赞

### 题目背景 ###

2020 年 6 月 8 日，国务院联防联控机制发布《关于加快推进新冠病毒核酸检测的实施意见》，提出对“密切接触者”等八类重点人群“应检尽检”，其他人群“愿检尽检”。

### 问题描述 ###

某市设有 n 个核酸检测点，编号从 1 到 n，其中 i 号检测点的位置可以表示为一个平面整数坐标 (xi,yi)。

为方便预约核酸检测，请根据市民所在位置 (X,Y)，查询距其最近的三个检测点。  
多个检测点距离相同时，编号较小的视为更近。

### 输入格式 ###

输入共 n+1 行。

第一行包含用空格分隔的三个整数 n、X 和 Y，表示检测点总数和市民所在位置。

第二行到第 n+1 行依次输入 n 个检测点的坐标。第 i+1 行（1≤i≤n）包含用空格分隔的两个整数 xi 和 yi，表示 i 号检测点所在位置。

### 输出格式 ###

输出共三行，按距离从近到远，依次输出距离该市民最近的三个检测点编号。

### 样例输入1 ###

3 2 2
    2 2
    2 3
    2 4

Data

### 样例输出1 ###

1
    2
    3

Data

### 样例输入2 ###

5 0 1
    -1 0
    0 0
    1 0
    0 2
    -1 2

Data

### 样例输出2 ###

2
    4
    1

Data

### 样例2解释 ###

![ecc54172382947bc84663bb49c839610.png][]

### 评测用例规模与约定 ###

全部的测试点满足，3≤n≤200，所有坐标均为整数且绝对值不超过 1000。

### 提示 ###

市民到第 i 号检测点的距离 Di 可由如下公式算出：

![b2972020ea5f433fbe592ac54443c0ea.png][]

>     # include<iostream>
>     using namespace std;
>     int main() {
>     	int n,X,Y;
>     	int xi,yi,di;
>     	int min1=99999999,index1=0;
>     	int min2=99999999,index2=0;
>     	int min3=99999999,index3=0;
>     	cin >> n >> X >> Y;
>     	for(int i=1;i<=n;i++){
>     		cin >> xi >> yi;
>     		di = (X-xi)*(X-xi) + (Y-yi)*(Y-yi);
>     		if(di<min1){
>     			min3=min2; index3=index2;
>     			min2=min1; index2=index1;			
>     			min1=di; index1=i;			
>     		}	
>     		else if(di<min2){
>     			min3=min2; index3=index2;
>     			min2=di; index2=i;			
>     		}
>     		else if(di<min3){
>     			min3=di; index3=i;			
>     		}
>     	}
>     	cout << index1 << endl;
>     	cout << index2 << endl;
>     	cout << index3 << endl;
>     	return 0;
>     }

[ecc54172382947bc84663bb49c839610.png]: https://img-blog.csdnimg.cn/ecc54172382947bc84663bb49c839610.png
[b2972020ea5f433fbe592ac54443c0ea.png]: https://img-blog.csdnimg.cn/b2972020ea5f433fbe592ac54443c0ea.png