結果

問題 No.622 点と三角柱の内外判定
コンテスト
ユーザー tnakao0123
提出日時 2018-01-04 13:50:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 1,500 ms
コード長 3,086 bytes
コンパイル時間 635 ms
コンパイル使用メモリ 85,440 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-23 03:37:02
合計ジャッジ時間 1,811 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:116:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  116 |     scanf("%lf%lf%lf", &ps[i].x, &ps[i].y, &ps[i].z);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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