AOJ 2159 Symmetry

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2159

問題概要

点が N 個与えられる．これらすべての点で，自己交差しないように辺を結ぶことで線対称な多角形を構成できるか判定せよ．
ただし，点は多角形の順番（反時計回り or 時計回り）であたえられるわけではない．

・制約
1 <= N <= 1000

解法

適当に2点を決めて，それの垂直二等分線を軸の候補とすると，全体で O(N^3) かかってしまうので間に合いません．

しかしよく考えると，凸包を作って，隣接する2点の垂直二等分線または向かい合う点同士を結んだ直線だけを候補として良いことがわかります．
これは自分で図を書いてみたほうがわかりやすいと思います．（線対称な凸でない多角形を書いてみて，その線と凸包を比べるとわかります．）

あとは線を引いた後に対称か判定するだけなんですが，小数点上で計算をするので，最終的に各点の座標を int に戻してやって，点の set の上で対称な位置に点があるかどうか見ればいいです．

コーナーケースは一直線上に点が並んでいるときで，最初にチェックしておきます．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ld = long double;

constexpr ld eps = 1e-8;
constexpr ld pi = std::acos(-1.0);

using pii = pair<int, int>;

// ライブラリは長いので略．

int main() {
    int N;
    cin >> N;
    set<pii> ps;
    polygon poly;
    double gx = 0, gy = 0;
    for(int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        gx += x;
        gy += y;
        ps.insert(make_pair(x, y));
        poly.emplace_back(x, y);
    }

    bool ok = false;
    // 一直線上に並んでいればNG
    for(int i = 2; i < N; ++i) {
        if(abs(cross(poly[1] - poly[i], poly[0] - poly[i])) > eps) {
            ok = true;
        }
    }
    if(!ok) {
        cout << "No" << endl;
        return 0;
    }

    sort(poly.begin(), poly.end(), [gx, gy](auto const& p1, auto const& p2) {
        return arg(p1 - point(gx, gy)) < arg(p2 - point(gx, gy));
    });
    poly = convex_hull(poly);
    vector<line> ls;
    int const m = poly.size();
    for(int i = 0; i < (int)poly.size(); ++i) {
        ls.emplace_back(poly[i], poly[i + m / 2]);
        ls.emplace_back(separate(poly[i], poly[(i + 1) % m]));
    }


    for(auto& l : ls) {
        ok = true;
        int on_line = 0;
        for(auto& p : ps) {
            auto ref = reflection(l, point(p.first, p.second));
            auto x = real(ref), y = imag(ref);
            if(abs(x - round(x)) > eps || abs(y - round(y)) > eps) {
                ok = false;
                break;
            }
            int ix = round(x), iy = round(y);
            if(ps.count(make_pair(ix, iy)) == 0) {
                ok = false;
                break;
            }
            on_line += make_pair(ix, iy) == p;
        }
        if(ok && on_line <= 2) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}