UVA 1595 Symmetry(暴力)

男娘i 2022-06-07 02:22 131阅读 0赞

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\}][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$][_le]N![$ \\le$][_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 10
    5 10 
    6 14

## Sample Output ##

YES 
    NO 
    YES

思路：

若存在对称抽，则其x坐标必定是所有点中最左边和最右边这两点的x坐标之和的一半（中点）。如何判断是否存在对称抽，就是判断所有点是否都有关于此假定对称抽对称的对应点（暴力枚取）。为避免中点x坐标是小数，输入所有点时x坐标乘以2。

#include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    int main()
    {
        int t,n,a,midx,maxx,minx,x[1005],y[1005];
        cin>>t;
        while(t--)
        {
            maxx=minx=0;
            cin>>n;
            for(int i=0;i<n;i++)
            {
                cin>>a>>y[i];
                x[i]=a*2;
                if(x[i]>x[maxx])    maxx=i;
                if(x[i]<x[minx])    minx=i;
            }
    
            midx=(x[maxx]+x[minx])/2;
    
            int i=0;
            for(;i<n;i++)
            {
                int flag=0;
                for(int j=0;j<n;j++)
                {
                    if(y[i]==y[j]&&(x[i]+x[j]==midx*2))
                    {
                        flag=1; break;
                    }
                }
                if(!flag)   break;
            }
    
            if(i>=n)
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
        }
        return 0;
    }

[epsfbox_p3226.eps]: /images/20220607/d398f72e70a740568849b10f32862c6f.png
[_le]: /images/20220607/bbc1532672cc42d9a29ea1ca67805932.png