Uva1595 对称轴

Uva 1595对称轴

题目描述:

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

Uva1595 对称轴

思路:

这个题我的思路是将所有高度(y)相同的点求每组高度的坐标x的平均值,如果总个数N是偶数,那么只要每组高度的x平均值相同,就能找到一个对称轴,而N是奇数,则需要平均值相同的基础上找出所有点的坐标x的中位数,如果中位数和平均值相同,那么也可以。

做的时候想的条件有些复杂,多加了一些没用的判断。这里提供两组测试数据,供参考。

2
4
-1 0
1 0
0 0 
0 -1
5
0 -1
0 10000
0 -10000
0 2
0 5
代码:
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    int T;
    //freopen("uva1595_in.txt", "r", stdin);
    //freopen("uva1595_out.txt", "w", stdout);
    cin >> T;
    while(T--){
        int n, N;
        cin >> n; N = n;
        int x, y;
        map<int, long long> height;
        map<int, float> hnums;
        vector<int> xvec;
        while(n--){
            cin >> x >> y;
            xvec.push_back(x);
            if(!height.count(y)) height[y] = x;
            else height[y] += x;
            if(!hnums.count(y)) hnums[y] = 1;
            else hnums[y] = hnums[y] + 1.0;
        }
        vector<float> means;
        int failed = 0;
        for(auto it = height.begin(); it != height.end(); ++it){
            float avrg = (*it).second / hnums[(*it).first];
            means.push_back(avrg);
        }
        
        for(int i = 0; i < means.size()-1; ++i){
            if( means[i] != means[i+1]){
                failed = 1;
                break;
            } 
        }       
        float avgr = means[0];
        if(!failed && N%2){
            sort(xvec.begin(), xvec.end());
            int mid = xvec[N/2];
            if(mid*2 != (int)(avgr*2)) failed = 1;  
        }
        int i;
        for(i = 0; i < xvec.size()-1; ++i){
            if(xvec[i] != xvec[i+1]) break;
        }
        if(i == xvec.size()-1) failed = 0; 
        if(!failed) cout << "YES\n";
        else cout << "NO\n";
        
    }
}
PS:

此外我还在网上看到两种方法,要比我上面的这个简单不少。

一是先找到x最大和最小的两个点,取他们的中点作为对称轴,因为如果整个图形对称,那么对称轴一定在最外面的两个点的中点上。然后对每个点遍历,看是否存在与之对称的点。

参看链接:https://blog.csdn.net/GuoZLH/article/details/53141335

二是直接对所有点按x大小分别升序和降序地排列一次,然后顺序地看point1[i].x + point2[i].x是否是中轴的二倍,然后再看y是否相同即可。中轴和方法一的做法一致。这个方法应该是最巧妙的。

参看链接:https://blog.csdn.net/Amateur_DP/article/details/81255412

上一篇:C#正则表达式基础


下一篇:【机器学习】k-means——航空用户聚类分析案例