对称轴

快来打我* 2022-06-12 04:56 99阅读 0赞

The figure shown on the left is left-right symmetric as it is possible to fold the sheet of paper along avertical line, drawn as a dashed line, and to cut the figure into two identical halves. The figure on theright 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.InputThe 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 dotsin a figure. Each of the following N lines contains the x-coordinate and y-coordinate of a dot. Bothx-coordinates and y-coordinates are integers between −10, 000 and 10, 000, both inclusive.OutputPrint exactly one line for each test case. The line should contain ‘YES’ if the figure is left-right symmetric,and ‘NO’, otherwise.

Sample Input

\-2 5

0 0

6 5

4 0

2 3

0 4

4 0

0 0

5 14

6 10

5 10

6 14

Sample Output

YES

题意：

有T个测试样例，每个测试样例有n个点，判断由着n 个点构成的图形是否左右对称，对称输出YES,否则输出NO

#include<cstring>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    struct A
    {
        int x,y;
    } f[1001],g[1001];
    bool cmp(A a,A b)
    {
        return a.x<b.x;
    }
    bool cmp1(A a,A b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y>b.y;
    }
    bool cmp2(A a,A b)
    {
        if(a.x!=b.x)
            return a.x<b.x;
        return a.y<b.y;
    }
    int main()
    {
        int n,m;
        scanf("%d",&n);
        while(n--)
        {
            int num=0,ok=0;
            int xx,yy,s=0,su=0;
            scanf("%d",&m);
            for(int i=0; i<m; i++)
            {
                scanf("%d %d",&g[i].x,&g[i].y);
                if(i==0)
                {
                    xx=g[i].x;
                    yy=g[i].y;
                }
                else
                {
                    if(xx==g[i].x)
                        s++;
                    if(yy==g[i].y)
                        su++;
                }
            }
            if(s==m-1||su==m-1)//当平行于x轴或者y轴的时候
            {
                printf("YES\n");
                continue;
            }
            sort(g,g+m,cmp);//先按x坐标从小到大排序，小的一部分在左边，大的在右边
            for(int i=0; i<m/2; i++)//找左边部分
            {
                f[i].x=g[i].x;
                f[i].y=g[i].y;
            }
            sort(f,f+m/2,cmp1);//左边部分先按x从小到大排序，当x相等时再按y从到大到小排序
            for(int i=m/2; i<m; i++)//找右边部分
            {
                f[i].x=g[i].x;
                f[i].y=g[i].y;
            }
            sort(f+m/2,f+m,cmp2);//右边部分先按x从小到大排序，当x相等时还是按y从到小到大排序
            if(m%2)
            {
                int x=m/2-1;
                int y=m/2+1;
                int temp=2*f[m/2].x;
                for(int i=0,j=m-1; i<m/2; i++,j--)
                {
                    if((f[i].x+f[j].x)!=temp&&f[i].x!=f[j].x)//如果这两点横坐标不对称，并且这里两点的横坐标不相等，图形就肯定是不对称的
                    {
                        ok=1;
                        printf("NO\n");
                        break;
                    }
                    else//横坐标对称（包括横坐标可以相等，也可以不相等）
                    {
                        if(f[i].y==f[j].y||(f[i].x==f[j].x))//y坐标相等或者横坐标相等（因为当横坐标不相等，y坐标相等时，这两点事对称的，这是一种情况，还有就是当横坐标相等时，他也是对称的，因为是平行于y轴啊），下面偶数情况也是一样的分析
                            num++;
                    }
                }
            }
            else
            {
                int x=m/2-1;
                int y=m/2;
                int temp=f[x].x+f[y].x;
                for(int i=0,j=m-1; i<m/2; i++,j--)
                {
                    if((f[i].x+f[j].x)!=temp&&f[i].x!=f[j].x)
                    {
                        ok=1;
                        printf("NO\n");
                        break;
                    }
                    else
                    {
                        if(f[i].y==f[j].y||(f[i].x==f[j].x))
                            num++;
                    }
                }
            }
            if(!ok)
            {
                if(num==m/2)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
        return 0;
    }

对称轴

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 Symmetry（对称轴）UVA 1595

相关对称轴（Symmetry）

相关对称轴