首页 > 代码库 > UVA - 1595
UVA - 1595
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
N1, 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.
The following shows sample input and output for three test cases.
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 105 10 6 14
Sample Output
YES NO YES
妈蛋这题的测试数据有问题，x 绝对 在【-10000,10000】之外，害得我RE了一天，操
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 #include <cmath> 7 using namespace std; 8 9 vector <int> v;10 vector<vector<int> > Hash(20002);11 12 int equal(double x,double y) {13 return (fabs(x - y) <= 1e-6?1:0);14 }15 16 int main () {17 int T;18 // freopen("1.in","r",stdin);19 cin >> T;20 while (T--) {21 int N;22 cin >> N;23 for (int i = 0;i < 20002;i++) {24 Hash[i].clear();25 }26 v.clear();27 int a[20002];28 memset(a,0,sizeof(a));29 int x,y;30 for (int i = 0;i < N;i++) {31 cin >> x >> y;32 y += 10000;33 if (a[y] == 0) {34 v.push_back(y);35 a[y]++;36 }37 Hash[y].push_back(x);38 }39 for (int i = 0;i < v.size();i++) {40 sort(Hash[v[i]].begin(),Hash[v[i]].end());41 }42 double mx = ((Hash[v[0]][0] + Hash[v[0]][Hash[v[0]].size() - 1])) * 1.0 / 2;43 // cout << mx << endl;44 int ok = 1;45 for (int i = 0;i < v.size();i++) {46 if (Hash[v[i]].size() == 1 && !equal(Hash[v[i]][0],mx)) {47 ok = 0;break;48 } 49 for (int j = 0;j < Hash[v[i]].size() && Hash[v[i]][j] < mx;j++) {50 double dis = mx - Hash[v[i]][j];51 int xx = Hash[v[i]][j] + int(dis * 2 + 0.5);52 if (Hash[v[i]][Hash[v[i]].size() - 1 - j] != xx) {53 ok = 0;54 break;;55 }56 } 57 if (ok == 0) break;58 }59 cout << (ok ? "YES" : "NO") << endl;60 }61 }
UVA - 1595