Yandex.Algorithm 2014 Round 3 E問題 - Tetrahedron

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 3
問題文

問題概要

$3$ 次元空間において,$xy$ 平面を地面とし,$z$ 軸に負の方向に重力が働いている.
四面体の $4$ 点の座標 $(x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3), (x_4,y_4,z_4)$ が与えられる.
ただし,$z_1=z_2=z_3$ で最初の $3$ 点は地面についており,$z_4 > 0$ を満たす.
この四面体は,「これから倒れる」か,「このまま安定して立っている」か,「両者の間で不安定な状態」かを判定する問題.

解法

重心の $x$ 座標と $y$ 座標 $(\frac{x_1+x_2+x_3+x_4}{4}, \frac{y_1+y_2+y_3+y_4}{4})$ が,地面に付いている三角形の内部か,外部か,辺上かを判定すれば良い.
それは,例えば,三角形の符号付き面積などを用いれば良い.

C++によるスパゲッティなソースコード

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

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

#define ll long long

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}

ll getd(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3){
  ll d;

  x2 -= x1; x3 -= x1;
  y2 -= y1; y3 -= y1;

  d = x2 * y3 - x3 * y2;
  if(d<0) return -1;
  if(d>0) return 1;
  return 0;
}

int X[4], Y[4], Z[4];

int main(){
  int i, j, k;
  int cX, cY, cZ;
  int f[3];

  rep(i,4) reader(X+i,Y+i,Z+i);
  rep(i,4) X[i]*=4, Y[i]*=4, Z[i]*=4;

  if(getd(X[0],Y[0],X[1],Y[1],X[2],Y[2])==-1){
    swap(X[1],X[2]);
    swap(Y[1],Y[2]);
  }

  cX = (X[0]+X[1]+X[2]+X[3]) / 4;
  cY = (Y[0]+Y[1]+Y[2]+Y[3]) / 4;
  cZ = (Z[0]+Z[1]+Z[2]+Z[3]) / 4;

  rep(i,3) f[i] = getd(X[i],Y[i],X[(i+1)%3],Y[(i+1)%3],cX,cY);

  if(f[0]==-1 || f[1]==-1 || f[2]==-1){ writer("Falling\n"); return 0; }
  if(f[0]== 0 || f[1]== 0 || f[2]== 0){ writer("Unstable\n"); return 0; }
  writer("Standing\n");

  return 0;
}

Current time: 2017年09月25日07時49分48秒
Last modified: 2014年08月06日01時26分00秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round3
トップページに戻る

Logged in as: unknown user (not login)

ログイン: