Symmetry UVA

The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along a vertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on the right is not left-right symmetric as it is impossible to find such a vertical line.

Write a program that determines whether a figure, drawn with dots, is left-right symmetric or not. The dots are all distinct.

Input

The input consists of T test cases. The number of test cases T is given in the first line of the input file. The first line of each test case contains an integer N, where N (1 ≤ N ≤ 1,000) is the number of dots in a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Both x-coordinates and y-coordinates are integers between −10,000 and 10,000, both inclusive.

Output

Print exactly one line for each test case. The line should contain ‘YES’ if the figure is left-right symmetric, and ‘NO’, otherwise.

Sample Input

Sample Output

YES

NO

HINT

题目的意思是要判断是否给定的点有一个和y轴平行的对称轴。采用的策略是分开判断，先先判断纵坐标相同的所有点是否围绕和对称，并且求出对称轴的二倍，就是两个最左和最右侧的坐标的和相同。其中一定要对做标数为奇数的进行一次单独处理，将排序后的数组中间的那个赋值一遍加入到数组再排序。判断完成后再对各个纵坐标所求的对称轴是否相同进行判断。

存储方式是使用map<int,vector>键为纵坐标，值为横坐标数组。然后对每一个纵坐标判断，并将结果存到一个数组中，最后对所有纵坐标求得值进行判断，如果相同输出YES否则NO。

注意：一定要处理相同纵坐标上得点得个数为奇数得情况。

Accepted

#include<iostream>

#include<algorithm>

#include<map>

#include<vector>

using namespace std;

int main()

{

	int m, n,a,b;

	cin >> m;

	while (m--) {	//m组数据

		cin >> n;	//每组数据的坐标数目

		map<int, vector<int> >arr;//键为纵坐标，值为横坐标数组

		vector<int>arry;	//存储纵坐标

		while (n--) {

			cin >> a >> b;	//录入坐标

			if (!arr.count(b))arry.push_back(b);//将纵坐标录入数组并查重

			arr[b].push_back(a);	//录入map

		}//while	n

		int flag = 0;		//标志位

		for (int i = 0;i < arry.size();i++) {//对每一个横坐标进行判断

			vector<int>temp;		//将键值复制出来

			temp = arr[arry[i]];

			sort(temp.begin(), temp.end());//排序

			if (temp.size() % 2) {

				temp.push_back(temp[temp.size() / 2]);//如果是奇数将中间的坐标再次压进数组

				sort(temp.begin(), temp.end());//再次排序

			}

			for (int j = 0;j < temp.size()/ 2;j++)//将两侧的横坐标两两相加并赋值给数组

				temp[j] = temp[temp.size() - 1 - j] = temp[j] + temp[temp.size() - 1 - j];

			sort(temp.begin(), temp.end());		//再次排序

			if (temp.front() == temp[temp.size() - 1])arry[i] = temp.front();//如果过首尾相同。说明纵坐标相同的所有点的横坐标是对称的，将凉凉相加的和赋给记录纵坐标的数组

			else {															//否则不是对称的，直接退出

				flag = 1;break;

			}//else

		}//for	i

		if (!flag) {	//如果过符合要求

			sort(arry.begin(), arry.end());		//如果过所有的元素相等，说明不同的纵坐标之间的对称轴也是相同的

			if (arry.front() == arry[arry.size() - 1])cout << "YES" << endl;

			else flag = 1;	//否则输出NO

		}

		if (flag)cout << "NO" << endl;

	}//while	m

}

巴特西

Symmetry UVA - 1595