题目:
3 2 2
2 2
2 3
2 4
样例输出
1
2
3
此题利用vector,或者结构体来排序比较好,主要考察的地方就是排序,1、根据距离排序,2、距离相同根据编号排序
代码如下
//结构体数组版本
#include <iostream>
#include<vector>
#include<math.h>
#include<algorithm>
using namespace std;
struct Point
{
int id;
int distance;
};
bool cmp(Point& a, Point& b)
{
if (a.distance == b.distance)
return a.id < b.id;
return a.distance < b.distance;
}
int main()
{
int n, x, y;
cin >> n >> x >> y;
int x1, y1;
Point p[205];
for (int i = 0; i < n; i++)
{
cin >> x1 >> y1;
p[i].id = i + 1;
p[i].distance = pow(x1 - x, 2) + pow(y1 - y, 2);
}
sort(p, p + n, cmp);
for (int i = 0; i < 3; i++)
{
cout << p[i].id << endl;
}
return 0;
}
另一个版本,这里可以直接传入vector数组,不经过map
当时想看看make_pair的使用方法,所以饶了一下
#include <iostream>
#include <math.h>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
typedef pair<int, int> PAIR;
bool cmp(const PAIR &a, const PAIR &b)
{
//距离相同时,比较编号大小
if (a.second == b.second)
{
return a.first < b.first;
}
//距离不同时,比较距离大小
return a.second < b.second;
}
int main()
{
int n, x, y;
cin >> n >> x >> y;
int x1, y1;
map<int, int> dis;
for (int i = 0; i < n; i++)
{
cin >> x1 >> y1;
dis.insert(make_pair(i + 1, pow((x - x1), 2) + pow((y - y1), 2)));
}
vector<PAIR> vec;
for (map<int, int>::iterator iter = dis.begin(); iter != dis.end(); iter++)
{
vec.push_back(make_pair(iter->first, iter->second));
}
sort(vec.begin(), vec.end(), cmp);
for (int i = 0; i < 3; i++)
{
cout << vec[i].first << endl;
}
return 0;
}
整理后的版本
#include <iostream>
#include<vector>
#include<math.h>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int, int> PAIR;
bool cmp(const PAIR& a, const PAIR& b)
{
//距离相同时,比较编号大小
if (a.second == b.second)
{
return a.first < b.first;
}
//距离不同时,比较距离大小
return a.second < b.second;
}
int main()
{
int n, x, y;
cin >> n >> x >> y;
vector<PAIR> p;
int x1, y1;
for (int i = 0; i < n; i++)
{
cin >> x1 >> y1;
p.push_back(make_pair(i + 1, pow((x - x1), 2) + pow((y - y1), 2)));
}
sort(p.begin(), p.end(), cmp);
for (int i = 0; i < 3; i++)
{
cout << p[i].first << endl;
}
return 0;
}