对称轴（Symmetry）

你的名字 2022-11-30 04:28 78阅读 0赞

给出平面上N（N≤1000）个点，问是否可以找到一条竖线，使得所有点左右对称。

/*对称轴一定是最左边和最右边点的中点所在竖线。 可以找最左边和最右边的点,即横坐标最小和最大。 主要是把点的横坐标排序， 然后判断左边的第n个点和右边的第n个点是否关于对称轴对称。 */
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    int n,m;
    struct point1
    { 
        double x;
        double y;
    };
    point1 p1[1010];
    struct point2
    { 
        double x;
        double y;
    };
    point2 p2[1010];
    bool cmp1(point1 l,point1 r)
    { 
        if(l.x==r.x)
      	return l.y<r.y;
        else
      	return l.x<r.x;
    }
    bool cmp2(point2 l,point2 r)
    { 
        if(l.x==r.x)
      	return l.y>r.y;
        else
      	return l.x<r.x;
    }
    int main()
    { 
        cin>>n;
        for(int t=0;t<n;t++)
        { 
      	bool f=0;
      	cin>>m;
      	for(int i=1;i<=m;i++)
      	{ 
                cin>>p1[i].x>>p1[i].y;
       	    p2[i].x=p1[i].x;
                p2[i].y=p1[i].y;
      	}
            sort(p1+1,p1+m+1,cmp1);
            sort(p2+1,p2+m+1,cmp2);
            double mid=(p1[1].x+p1[m].x)/2;
            int l=1,r=m;
            while(l<=r)
      	{ 
                if(mid-p1[l].x!=p1[r].x-mid||p1[l].y!=p2[r].y)
                { 
        		cout<<"NO"<<endl;
        		f=1;
        		break;
                }
                l++;
                r--;
            }
            if(f==0)
            { 
       	    cout<<"YES"<<endl;
      	}
        }
        return 0;
    }