aoj 2442 ConvexCut

問題

問題概要

与えられた図形が、点Pを通るどのような直線で切ったとしても、面積を2等分する点Pが存在するかどうかを求める問題。

解法

点対称のような図形になればいい。なんて言えばいいかわからないけど、角張った円のような。(重心関して点対称であればいいみたい。)そのためにはまず、点が偶数個なければならない。そして 、すべての辺の長さが等しければいい。さらに、対角線となりうるすべての辺の共有点が１点(それぞれの辺の中点)で交わっていれば良い。
具体的な実装は対象と成りうる点の中点を全て比較して、全てが一致し、さらに、与えられた図形の辺が全て等しいかを見ている。

ミス

1WA
はじめは、すべての対角線が一点で交わっていればいいと考えた。しかし、これだと台形のような形も含んでしまうので、すべての辺が等しいという条件いれた。重心とか考えればスムーズに行けたかな。

コード

/*
長さだけだと不十分なことは明らか
対象と成りうる点の中点を全て比較して、全てが一致していれば十分条件　例外台形
*/
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(ll i=0;i<(n);i++)

const double EPS = 1e-14;
int main(void){
    ll n; cin >> n;
    vector<pair<double, double> > point(n);//fi　;x座標　 se ;y座標
    rep(i, n) scanf("%lf %lf", &point[i].fi, &point[i].se);

    //nが奇数はありえない
    if(n % 2 == 1){
        printf("NA\n");
        return 0;
    }

    //長さチェック
    vector<double> len(n);
    rep(i, n - 1){
        double tmp = pow(point[i + 1].fi - point[i].fi, 2) + pow(point[i + 1].se - point[i].se, 2);
        len.push_back(tmp);
    }
    double tmp = pow(point[0].fi - point[n - 1].fi, 2) + pow(point[0].se - point[n - 1].se, 2);
    len.push_back(tmp);
    sort(all(len));
    if(len[n - 1] - len[0] > EPS){
        printf("NA\n");
        return 0;
    }

    //対象と成り得る点の中点を求める
    vector<double> Px;
    vector<double> Py;
    rep(i, n / 2){
        double x = (point[i].fi + point[i + n / 2].fi) / 2.0;
        Px.push_back(x);
        double y = (point[i].se + point[i + n / 2].se) / 2.0;
        Py.push_back(y);
    }

    //上で求めた対象と成りうる点をソートして、大きいものと小さいものが一致していれば、点対象である
    sort(all(Px));
    if(Px[n / 2 - 1] - Px[0] > EPS){
        printf("NA\n");
        return 0;
    }
    sort(all(Py));
    if(Py[n / 2 - 1] - Py[0] > EPS){
        printf("NA\n");
        return 0;
    }

    printf("%.9f %.9f\n", Px[0], Py[0]);
    return 0;
}