UVA1595 Symmetry 对称轴 解题报告

题目链接

https://vjudge.net/problem/UVA-1595

题目大意

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

解题思路

使用map< double, vector< double > > 将所有的点按照y轴分类存放，按y值一行行遍历所有的点，如果真的存在一个对称轴使得所有的点左右对称的话，那么这个对称轴的x坐标一定是任意一行相距最远的两个点的中间值（即他们的和除以2），这里我们就取第一行的最远两点求出中间值，然后遍历每一行的时候都从最靠外的两个点开始从外到内配对算他们的中间值，如果全部都等于同一个中间值，则确实存在这么一条竖线使得所有点左右对称。具体实现细节见代码和注释。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define endl '\n';
const int maxn = 1e3 + 10;
const int INF = 0x3fffffff;
const int mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    // 将所有点按照y轴分类存放
    map<double, vector<double>> xofy;
    for (int i = 0; i < n; i++) {
        double x, y;
        cin >> x >> y;
        xofy[y].push_back(x);
    }
    // 按y轴一行一行遍历所有的点
    bool first = true;
    double midx = 0;
    for (auto e : xofy) {
        auto vec = e.second;
        sort(vec.begin(), vec.end());
        if (first) {
            first = false;
            midx = (vec.front() + vec.back()) / 2;    // 如果真的存在一个对称轴的话，那么这个对称轴的x坐标一定是任意一行的最远两个点的中轴
        }
        for (int i = 0; i < vec.size() / 2; i++) {
            if ((vec[i] + vec[vec.size() - 1 - i]) / 2 != midx) {
                cout << "NO\n";
                return;
            }
        }
        if (vec.size() % 2 != 0) {
            if (vec[vec.size() / 2] != midx) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}