多边形的对称轴 - O興~ - 歪酷博客 Ycool Blog

今天做了一道求一个多边形是否存在对称轴的题。主要是要想到一点：如果有对称轴，则对称轴左、右两边的顶点数应该相等，并且两两对称。所以对称轴肯定经过某一顶点或某一条边的中点。具体分两种情况：如果多边形的顶点数为奇数，则对称轴肯过经过一个顶点和它对边的中点；如果多边形的顶点数为偶数，则对称轴要么过两个顶点，要么过两条对边的中点。
原题在UVA10416(online-judge.uva.es/p/v104/10416.html)，是刘汝佳出的哦。

应陈力的要求，我把代码贴在这里。写得有点乱。其实还可以写得再好看一点。只要把每条边的中点也加到多边形中，那么就只有一种情况，就是总共有偶数个顶点，对称轴一定过某两个顶点。

#include <iostream>

using namespace std;

//<reused_codes>
struct XY;

inline double crsProd(const XY&, const XY&);
inline double dotProd(const XY&, const XY&);

//A 2-dimensional point or vector.
struct XY {
    double x;
    double y;

    void set(double _x, double _y) {
        x = _x;
        y = _y;
    }

    XY operator - (const XY& other) const {
        XY result = {x - other.x, y - other.y};
        return result;
    }

    XY operator + (const XY& other) const {
        XY result = {x + other.x, y + other.y};
        return result;
    }

    XY operator / (double d) const {
        XY result = {x / d, y / d};
        return result;
    }

    //Square of the length of this vector. Sometimes you just want to compare
    //the lengths of two vectors, so you needn't calculate the square roots.
    double normSqr() const {
        return x * x + y * y;
    }
};

//Cross product of vector a and b
inline double crsProd(const XY& a, const XY& b) {
    return a.x * b.y - b.x * a.y;
}

//Dot product of vector a and b
inline double dotProd(const XY& a, const XY& b) {
    return a.x * b.x + a.y * b.y;
}

//Whether point a and b are symmetric about line (axis1, axis2).
bool isSymm(const XY& a, const XY& b, const XY& axis1, const XY& axis2) {
    return dotProd(a - b, axis1 - axis2) == 0.0
           && (a - axis1).normSqr() == (b - axis1).normSqr();
}
//</reused_codes>

const int MAX_POINT = 100;

XY g_point[MAX_POINT];
int g_pntCnt;

bool solveEven() {
    bool symm = false;
    int halfCnt = g_pntCnt / 2;
    for (int i = 0; i < halfCnt && !symm; i++) {
        symm = true;
        XY axis1 = g_point[i];
        XY axis2 = g_point[(i + halfCnt ) % g_pntCnt];
        for (int j = 1; j < halfCnt && symm; j++) {
            XY left = g_point[(i + j) % g_pntCnt];
            XY right = g_point[(i + g_pntCnt - j) % g_pntCnt];
            if (!isSymm(left, right, axis1, axis2)) {
                symm = false;
            }
        }
        if (!symm) {
            symm = true;
            XY axis1 = (g_point[i] + g_point[(i + 1) % g_pntCnt]) / 2.0;
            XY axis2 = (g_point[(i + halfCnt) % g_pntCnt]
                        + g_point[(i + halfCnt + 1) % g_pntCnt]
                       ) / 2.0;
            for (int j = 1; j < halfCnt && symm; j++) {
                XY left = g_point[(i + j) % g_pntCnt];
                XY right = g_point[(i + g_pntCnt - j + 1) % g_pntCnt];
                if (!isSymm(left, right, axis1, axis2)) {
                    symm = false;
                }
            }
        }
    }
    return symm;
}

bool solveOdd() {
    bool symm = false;
    int halfCnt = g_pntCnt / 2;
    for (int i = 0; i < g_pntCnt && !symm; i++) {
        symm = true;
        XY axis1 = g_point[i];
        XY axis2 = (g_point[(i + halfCnt) % g_pntCnt]
                    + g_point[(i + halfCnt + 1) % g_pntCnt]
                   ) / 2.0;
        for (int j = 1; j <= halfCnt && symm; j++) {
            XY left = g_point[(i + j) % g_pntCnt];
            XY right = g_point[(i + g_pntCnt - j) % g_pntCnt];
            if (!isSymm(left, right, axis1, axis2)) {
                symm = false;
            }
        }
    }
    return symm;
}

void solve() {
    bool symm;
    if (g_pntCnt % 2 == 0) {
        symm = solveEven();
    }
    else {
        symm = solveOdd();
    }
    if (symm) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

void input() {
    cin >> g_pntCnt;
    for (int i = 0; i < g_pntCnt; i++) {
        cin >> g_point[i].x >> g_point[i].y;
    }
}

int main() {
    int caseCnt;
    cin >> caseCnt;
    for (int i = 0; i < caseCnt; i++) {
        input();
        solve();
    }
    return 0;
}