AOJ 2442 ConvexCut
解法
答えがあるとしたら, それは重心以外ありえません。重心が答えになるとき, 図形は重心に関して点対称になっているはずです。素直にそれを実装しましょう。
typedef long double Real; Real eps = 1e-12; Real add(Real a, Real b) { if (abs(a+b) < eps * (abs(a)+abs(b))) return 0; return a+b; } bool equal(Real a, Real b) { return add(a, -b) == 0; } struct P { Real x, y; P() {} P(Real x, Real y) : x(x), y(y) {} P operator+(P p) const {return P(add(x, p.x), add(y, p.y));} P operator-(P p) const {return P(add(x, -p.x), add(y, -p.y));} P operator*(Real d) const {return P(x*d, y*d);} Real dot(P p) const {return add(x*p.x, y*p.y);} // 内積 Real det(P p) const {return add(x*p.y, -y*p.x);} // 外積 Real dist(P p) const {return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));} // 距離 void normalize() {Real d = sqrt(x*x+y*y); x /= d; y /= d;} // 正規化 bool operator<(const P& rhs) const { if (x != rhs.x) return x < rhs.x; return y < rhs.y; } bool operator==(const P& rhs) const { return equal(x, rhs.x) && equal(y, rhs.y); } }; // 線分p1-p2上に点qがあるかを判定する bool on_seg(P p1, P p2, P q) { return (p1-q).det(p2-q) == 0 && (p1-q).dot(p2-q) <= 0; } // 直線p1-p2と直線q1-q2が平行かどうかの判定 bool parallel(P p1, P p2, P q1, P q2) { P a = p2-p1; P b = q2-q1; return a.det(b) == 0; } const int MAXN = 55; P pnts[MAXN]; int n; void solve() { if (n % 2 == 1) { cout << "NA" << endl; return; } Real ax = 0, ay = 0; for (int i = 0; i < n; i++) { ax += pnts[i].x; ay += pnts[i].y; } ax /= n; ay /= n; P a(ax, ay); for (int i = 0; i < n/2; i++) { if (!on_seg(pnts[i], pnts[i+n/2], a) || a.dist(pnts[i]) != a.dist(pnts[i+n/2])) { cout << "NA" << endl; return; } } printf("%.10Lf %.10Lf\n", ax, ay); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> pnts[i].x >> pnts[i].y; solve(); return 0; }