2014 Yandex.Algorithm Elimination Stage, Round 3 E - Tetrahedron

問題文

解法

Standing -> 重心をおろした位置が底面の内部
Unstable -> 重心をおろした位置が底面の周上にある
Falling -> 重心をおろした位置が底面の外部

重心の座標は (a + b + c + d) / 4 なので，あとは底面の三角形と点との内外判定をするだけ．

ソースコード

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

using ld = long double;
using point = complex<ld>;
using polygon = vector<point>;

constexpr ld eps = 1e-10;
constexpr ld pi = acos(-1.0);

class segment {
public:
    segment(point p1, point p2)
    : a(p1), b(p2)
    {}

    point a, b;
};

bool isis_sp(segment s, point p) {
    return std::abs(s.a - p) + std::abs(s.b - p) - std::abs(s.b - s.a) < eps;
}


int is_in_polygon(polygon const& poly, point p) {
    const int n = poly.size();
    ld sum = 0;
    for(int i = 0; i < n; ++i) {
        point p1 = poly[i], p2 = poly[(i + 1) % n];
        if(isis_sp(segment(p1, p2), p)) {
            return 0;
        }
        sum += arg((p2 - p) / (p1 - p));
    }
    return std::abs(sum) < pi / 2 ? 2 : 1;
}

int main() {
    vector<double> x(4), y(4), z(4);
    for(int i = 0; i < 4; ++i) {
        cin >> x[i] >> y[i] >> z[i];
    }

    point g(accumulate(begin(x), end(x), 0.0) / 4, accumulate(begin(y), end(y), 0.0) / 4);
    polygon poly;
    for(int i = 0; i < 3; ++i) {
        poly.emplace_back(x[i], y[i]);
    }

    switch(is_in_polygon(poly, g)) {
        case 0: cout << "Unstable" << endl; break;
        case 1: cout << "Standing" << endl; break;
        case 2: cout << "Falling" << endl; break;
        default: assert(false);
    }
}

感想

これ競プロの問題としてどうなの．