AOJ 2442 Convex-Cut

問題

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

問題概要

N 個の頂点からなる凸多角形が与えられる．このとき，ある点があって，その点を通る任意の直線がこの多角形を二等分することができるだろうか？できる場合は，その点の座標を求めよ．

自分が解いた時の流れ

任意の直線で二等分だからかなり制約がきつそう．点対称とかそんなんじゃないの？（適当）
→なんか通った

多少厳密（？）な証明

仮にそういう点Pがあったとして，Pを通り，それぞれ異なる直線を2本引く．
すると，明らかに，この多角形は4つの領域A, B, C, Dに分割される．

A+B = C+D かつ A+D = B+C より，A = C かつ B = D であることがわかる．つまり，向かい合う領域の面積が等しい．
ここで，向かい合う領域が共に三角形となるように直線を引くことができる（図の右側）．そして，図のように辺の長さを a, b, c, d とおくと，向かい合う領域の面積が等しいことから a * b == c * d が成り立つ．ここで，2本の直線を限りなく近づけていくと，a ≒ b, c ≒ d と近似できるので，a == d と考えることができる．
これはつまり，点Pに直線を一本引いたときに，凸多角形と2点で交わるが，その2点は点Pに関して点対称の位置にあるということ．直線は任意に引けるので，結局，凸多角形の辺上の任意の点は点Pに関して点対称（凸多角形が点対称）であるということ．

よって，Nが奇数のときは点対称にならないのでNA．
Nが偶数のときは，点対称となっているかを調べればよい．これは i 番目の頂点と i + N/2 番目の頂点を調べていけば十分．

計算量は O(N)．

ソースコード

#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
 
constexpr double eps = 1e-10;
 
int main() {
    int N;
    cin >> N;
    vector<double> x(N), y(N);
    for(int i=0; i<N; ++i) {
        cin >> x[i] >> y[i];
    }
    if(N % 2 == 1) {
        cout << "NA" << endl;
    } else {
        double px = (x[0] + x[N/2]) / 2, py = (y[0] + y[N/2]) / 2;
        bool ok = true;
        for(int i=0; i<N; ++i) {
            double vx = px - x[i], vy = py - y[i];
            ok &= fabs(px + vx - x[(i+N/2) % N]) < eps && fabs(py + vy - y[(i+N/2)%N]) < eps;
        }
        if(ok) {
            cout << fixed << setprecision(10) << px << " " << py << endl;
        } else {
            cout << "NA";
        }
    }
}