算法竞赛入门经典第二版习题5-6 对称轴 Symmetry uva1595

本文主要是介绍算法竞赛入门经典第二版习题5-6 对称轴 Symmetry uva1595，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：https://vjudge.net/problem/UVA-1595

思路：动用两个容器，一个容器存下所有坐标（vector< pair< int>,int>用pair存下点的x、y坐标），另一个容器记录按纵坐标分类的点的横坐标（map< int, set< int> >关键字是纵坐标，set里存的是对应纵坐标的横坐标，set有序，因此是由小到大排列）。对第一容器排序，取最大和最小的横坐标，其平均值即为可能的对称轴。接下来只要判断是否所有纵坐标相同的点其从两侧到中间每一对横坐标都等于那个对称轴即可。

代码：

#include <iostream>
#include <string>
#include <cstdio>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;int UNINIT = -20000;map<int, set<int> > ydata;//(y,x)
vector<pair<int, int> > data;
double ans;bool judge()
{ans = data[0].first*0.5+data[data.size()-1].first*0.5;for(map<int, set<int> >::iterator it = ydata.begin(); it!=ydata.end(); ++it){set<int>::iterator op = (it->second).begin();set<int>::iterator ed = --(it->second).end();for(int i=0; i<=(it->second).size()/2; i++, op++, ed--){if(*op*0.5+*ed*0.5!=ans){return false;}}}return true;
}int main()
{int T;cin >> T;while(T--){data.clear();ydata.clear();int n;cin >> n;for(int i=0; i<n; i++){int x, y;cin >> x >> y;data.push_back(make_pair(x, y));ydata[y].insert(x);}sort(data.begin(), data.end());if(judge()){cout << "YES" << endl;}else{cout << "NO" << endl;}}return 0;
}