結果

問題 No.622 点と三角柱の内外判定
ユーザー tnakao0123tnakao0123
提出日時 2018-01-04 13:50:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,500 ms
コード長 3,086 bytes
コンパイル時間 707 ms
コンパイル使用メモリ 84,492 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-24 18:53:53
合計ジャッジ時間 2,328 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,384 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,380 KB
testcase_15 AC 2 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 AC 2 ms
4,376 KB
testcase_22 AC 2 ms
4,380 KB
testcase_23 AC 2 ms
4,376 KB
testcase_24 AC 1 ms
4,376 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 1 ms
4,380 KB
testcase_30 AC 2 ms
4,380 KB
testcase_31 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 622.cc: No.622 点と三角柱の内外判定 - yukicoder
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

/* typedef */

template <typename T>
struct Pt3d {
  T x, y, z;

  Pt3d() {}
  Pt3d(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {}
  Pt3d(const Pt3d& pt) : x(pt.x), y(pt.y), z(pt.z) {}

  bool operator==(const Pt3d pt) const {
    return x == pt.x && y == pt.y && z == pt.z;
  }
  Pt3d<T> operator+(const Pt3d pt) const {
    return Pt3d<T>(x + pt.x, y + pt.y, z + pt.z);
  }
  Pt3d<T> operator-() const {
    return Pt3d<T>(-x, -y, -z);
  }
  Pt3d<T> operator-(const Pt3d pt) const {
    return Pt3d<T>(x - pt.x, y - pt.y, z - pt.z);
  }
  Pt3d<T> operator*(T t) const {
    return Pt3d<T>(x * t, y * t, z * t);
  }
  Pt3d<T> operator/(T t) const {
    return Pt3d<T>(x / t, y / t, z / t);
  }
  T dot(Pt3d v) const { return x * v.x + y * v.y + z * v.z; }
  Pt3d<T> cross(Pt3d v) const {
    return Pt3d<T>(y * v.z - z * v.y, z * v.x - x * v.z, x * v.y - y * v.x);
  }
  Pt3d<T> mid(const Pt3d pt) {
    return Pt3d<T>((x + pt.x) / 2, (y + pt.y) / 2, (z + pt.z) / 2);
  }
  T d2() { return x * x + y * y + z * z; }
  double d() { return sqrt(d2()); }

  Pt3d<T> rotx(double th) {
    double c = cos(th), s = sin(th);
    return Pt3d<T>(x, c * y - s * z, s * y + c * z);
  }

  Pt3d<T> roty(double th) {
    double c = cos(th), s = sin(th);
    return Pt3d<T>(s * z + c * x, y, c * z - s * x);
  }

  Pt3d<T> rotz(double th) {
    double c = cos(th), s = sin(th);
    return Pt3d<T>(c * x - s * y, s * x + c * y, z);
  }

  Pt3d<T> rotx90() { return Pt3d<T>(x, -z, y); }
  Pt3d<T> roty90() { return Pt3d<T>(z, y, -x); }
  Pt3d<T> rotz90() { return Pt3d<T>(-y, x, z); }

  bool operator<(const Pt3d& pt) const {
    return (x < pt.x || (x == pt.x && (y < pt.y || (y == pt.y && z < pt.z))));
  }

  void print(string format) {
    printf(("(" + format + ", " + format + ", " + format + ")\n").c_str(),
	   x, y, z);
  }
  void print() { print("%.6lf"); }
};

typedef Pt3d<double> pt;

/* subroutines */

/* global variables */

pt ps[4], nvs[3];

/* subroutines */

/* main */

/*
 p = t*nv+q
 (p-p0)*nv=(t*nv+q-p0)*nv=0 -> t*(nv*nv)=(p0-q)*nv -> t = (p0-q)*nv/(nv*nv)
 */

int main() {
  for (int i = 0; i < 4; i++)
    scanf("%lf%lf%lf", &ps[i].x, &ps[i].y, &ps[i].z);
  pt &q = ps[3];

  pt nv((ps[1] - ps[0]).cross(ps[2] - ps[0]));
  double t = (ps[0] - q).dot(nv) / nv.d2();
  pt p(nv * t + q);
  //p.print();

  for (int i = 0; i < 3; i++) {
    pt v0(ps[(i + 1) % 3] - ps[i]), v1(p - ps[i]);
    nvs[i] = v0.cross(v1);
    //nvs[i].print();
  }

  for (int i = 0; i < 3; i++) {
    double d = nvs[i].dot(nvs[(i + 1) % 3]);
    //printf("%lf\n", d);
    if (d <= 0.0) {
      puts("NO");
      return 0;
    }
  }

  puts("YES");
  return 0;
}
0