首页 > 代码库 > UVA - 1595

UVA - 1595

2024-08-03 14:07:58   217人阅读

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.

 

\epsfbox{p3226.eps}

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$ \le$N$ \le$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.

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 }
View Code

 

UVA - 1595


联系
我们