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
3
5
-2 5
0 0
6 5
4 0
2 3
4
2 3
0 4
4 0
0 0
4
5 14
6 10
5 10
6 14
Sample Output
YES
NO
YES
题目类型：暴力枚举
算法分析：由于判断的是是否存在左右对称，所以依次检查输入数据的每个y坐标，然后对于同一个y坐标，递增排序x坐标并从两头同时检查xa和xb中点的x坐标是否完全相同(对于所有的y坐标而言)
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
/************************************************** filename :f.cpp author :maksyuki created time :2018/1/22 21:38:32 last modified :2018/1/22 21:55:44 file location :C:\Users\abcd\Desktop\TheEternalPoet ***************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("in", "r", stdin) #define CFO freopen ("out", "w", stdout) #define CPPFF ifstream cin ("in") #define CPPFO ofstream cout ("out") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define DBT printf("time used: %.2lfs\n", (double) clock() / CLOCKS_PER_SEC) #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; map<int, vector<int>> ma; int main() { #ifdef LOCAL CFF; //CFO; #endif int t; scanf("%d", &t); while(t--) { ma.clear(); int n, va, vb; scanf(" %d", &n); for(int i = 1; i <= n; i++) { scanf("%d %d", &va, &vb); ma[vb].emplace_back(va * 2); } bool is_symc = true, is_first = true; int ta = -1, tb = -1; for(map<int, vector<int>>:: iterator it = ma.begin(); it != ma.end(); it++) { if(!is_symc) break; int ty = it->first, ylen = ma[it->first].size(); sort(ma[ty].begin(), ma[ty].end()); for(int i = 0; i <= ylen / 2; i++) { if(is_first) { ta = (ma[ty][i] + ma[ty][ylen-1-i]) / 2; is_first = false; } else { tb = (ma[ty][i] + ma[ty][ylen-1-i]) / 2; if(ta != tb) { is_symc = false; break; } } } } if(is_symc) puts("YES"); else puts("NO"); } return 0; } |
- « 上一篇：uva10391
- uva230：下一篇 »