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); } }
感想
これ競プロの問題としてどうなの.