Problem:


宇宙船 UAZ アドバンス号

 恒星歴 2005.11.5。あなたは宇宙船 UAZ アドバンス号の艦長として敵の宇宙船と交戦しようとしています。 幸い敵の宇宙船はまだこちらに気付かずに静止しています。また、すでに敵の宇宙座標は判明しており強力な直線のビームを放つ「フェザー砲」は発射準備を完了しています。あとは、発射命令を出すばかりです。

ところが、宇宙空間には、敵の設置したエネルギーバリアが存在しています。バリアは三角形をしており「フェザー砲」のビームをはね返してしまいます。また、ビームがバリアに当たれば敵に気付かれて逃げられてしまいます。事前に命中すると判定できなければ、発射命令は出せません。

そこで、UAZ アドバンス号、敵、バリアの位置の宇宙座標(3次元座標 x, y, z) を入力して、ビームがバリアをさけて敵に命中する場合は "HIT"、バリアに当たってしまう場合"MISS"と出力するプログラムを作成してください。

 ただし、バリアはアドバンス号から 3 角形に見えるものだけが対象であり、線分につぶれて見えるものはないものとします。また、バリアは 3 角形の頂点を含む境界でも有効であり、ビームをはね返すものとします。また、敵がバリア内にいる場合は"MISS"と出力して下さい。

x, y, z )を入力して、「フェ
ザー砲」がバリアをさけて敵に命中する場合は“HIT”、バリアに命中してはね返されてしまう場合“MISS”と出力し
て終了するプログラムを作成してください。

 ただし、バリアはアドバンス号から 3 角形に見えるものだけが対象であり、線分につぶれて見えるものはないも
のとします。また、バリアは 3 角形の頂点を含む境界でも有効であり、ビームをはね返すものとします。

-->

Input

入力データの形式は以下のとおりです：

1 行目は、UAZ アドバンス号の座標 (x, y, z) (整数、半角空白区切り)

2 行目は、敵の座標 (x, y, z) (整数、半角空白区切り)

3 行目は、バリアの頂点 1 の座標 (x, y, z) (整数、半角空白区切り)

4 行目は、バリアの頂点 2 の座標 (x, y, z ) (整数、半角空白区切り)

5 行目は、バリアの頂点 3 の座標 (x, y, z ) (整数、半角空白区切り)

Output

HIT または MISS と１行に出力してください。

Constraints

-100 ≤ x, y, z ≤ 100

UAZ アドバンス号と敵が同じ位置にいることはない。

Sample Input 1

-10 0 0
10 0 0
0 10 0
0 10 10
0 0 10

Output for the Sample Input 1

HIT

Sample Input 2

-10 6 6
10 6 6
0 10 0
0 10 10
0 0 10

Output for the Sample Input 2

MISS



Sample input:
-10 0 0
10 0 0
0 10 0
0 10 10
0 0 10


Sample output:
HIT

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import random

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def det(a, b, c):
    return + a[0] * b[1] * c[2] \
           + a[2] * b[0] * c[1] \
           + a[1] * b[2] * c[0] \
           - a[2] * b[1] * c[0] \
           - a[1] * b[0] * c[2] \
           - a[0] * b[2] * c[1]

def sub(v0, v1):
    # v0 - v1
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])

# me
p0 = list(map(int, input().split()))

# enemy
p1 = list(map(int, input().split()))

# barrier
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

def solve(p0, p1, A, B, C):
    a = sub(p1, p0)
    b = sub(A, B)
    c = sub(A, C)
    d = sub(A, p0)

    EPS = 0.0000001
    lower = -EPS
    upper = 1 + EPS

    denom = det(a, b, c)

    if denom != 0:
        t = det(d, b, c) / denom
        u = det(a, d, c) / denom
        v = det(a, b, d) / denom

        if t < lower:
            return 'HIT'

        # hit barrier
        elif lower < t < upper and lower <= u <= upper and lower <= v <= upper and lower <= u + v <= upper:
            return 'MISS'

        else:
            return 'HIT'
    else:
        return 'HIT'

def correct_solve(p0, p1, A, B, C):
    from fractions import Fraction
    def gauss(a):
        if not a or len(a) == 0: return None
        n = len(a)
        for i in range(n):
            if a[i][i] == 0:
                for j in range(i + 1, n):
                    if a[j][i] != 0:
                        for k in range(i, n + 1): a[i][k] += a[j][k]
                        break
                else:
                    return None
            for j in range(n):
                if i != j:
                    r = Fraction(a[j][i], a[i][i])
                    for k in range(i, n + 1): a[j][k] = a[j][k] - a[i][k] * r
        for i in range(n):
            x = Fraction(a[i][i], 1)
            for j in range(len(a[i])):
                a[i][j] /= x
        return a


    uaz = p0
    enemy = [0] + [-x + y for x, y in zip(p1, uaz)]
    b0 = [1] + [x - y for x, y in zip(A, uaz)]
    b1 = [1] + [x - y for x, y in zip(B, uaz)]
    b2 = [1] + [x - y for x, y in zip(C, uaz)]
    sol = gauss(list(map(list, zip(b0, b1, b2, enemy, [1, 0, 0, 0]))))
    if sol and all(0 <= e[-1] <= 1 for e in sol):
        return 'MISS'
    else:
        return 'HIT'

def rand_v():
    return (random.randrange(-100, 100), random.randrange(-100, 100), random.randrange(-100, 100))

if __name__ == '__main__':
    res = solve(p0, p1, A, B, C)
    print(res)


    # while True:
    #     p0 = rand_v()
    #     p1 = rand_v()
    #     A = rand_v()
    #     B = rand_v()
    #     C = rand_v()
    #     result0 = solve(p0, p1, A, B, C)
    #     result1 = correct_solve(p0, p1, A, B, C)
    #
    #     if result0[0] != result1[0]:
    #         print(p0, p1, A, B, C)
    #         print(result0)
    #         print(result1)
    #     else:
    #         print('same')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import random

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def det(a, b, c):
    return + a[0] * b[1] * c[2] \
           + a[2] * b[0] * c[1] \
           + a[1] * b[2] * c[0] \
           - a[2] * b[1] * c[0] \
           - a[1] * b[0] * c[2] \
           - a[0] * b[2] * c[1]

def sub(v0, v1):
    # v0 - v1
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])

# me
p0 = list(map(int, input().split()))

# enemy
p1 = list(map(int, input().split()))

# barrier
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a = sub(p1, p0)
b = sub(A, B)
c = sub(A, C)
d = sub(A, p0)

EPS = 0.0000001
lower = -EPS
upper = 1 + EPS

denom = det(a, b, c)

if denom != 0:
    t = det(d, b, c) / denom
    u = det(a, d, c) / denom
    v = det(a, b, d) / denom

    if t < lower:
        print('HIT')

    # hit barrier
    elif lower < t < upper and lower <= u <= upper and lower <= v <= upper and lower <= u + v <= upper:
        print('MISS')

    else:
        print('HIT')
else:
    print('HIT')

Submission status: Accepted

Solution code:
#!/usr/bin/python
from fractions import Fraction
import sys
if sys.version_info[0]>=3: raw_input=input

def gauss(a):
	if not a or len(a)==0: return None
	n=len(a)
	for i in range(n):
		if a[i][i]==0:
			for j in range(i+1,n):
				if a[j][i]!=0:
					for k in range(i,n+1): a[i][k]+=a[j][k]
					break
			else:
				return None
		for j in range(n):
			if i!=j:
				r = Fraction(a[j][i],a[i][i])
				for k in range(i,n+1): a[j][k] = a[j][k] - a[i][k]*r
	for i in range(n):
		x=Fraction(a[i][i],1)
		for j in range(len(a[i])):
			a[i][j] /= x
	return a

uaz=list(map(int,raw_input().split()))
enemy=[0]+[-x+y for x,y in zip(map(int,raw_input().split()),uaz)]
b0=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
b1=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
b2=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
sol=gauss(list(map(list,zip(b0,b1,b2,enemy,[1,0,0,0]))))
print('MISS' if sol and all(0<=e[-1]<=1 for e in sol) else 'HIT')

Submission status: Accepted

Solution code:
def get_det(a, b, c):
    a1, a2, a3 = a
    b1, b2, b3 = b
    c1, c2, c3 = c
    return a1 * b2 * c3 + a3 * b1 * c2 + a2 * b3 * c1 \
            - a3 * b2 * c1 - a2 * b1 * c3 - a1 * b3 * c2

def solve():
    import sys
    f_i = sys.stdin
    
    Sx, Sy, Sz = map(int, f_i.readline().split())
    Ex, Ey, Ez = map(int, f_i.readline().split())
    B1x, B1y, B1z = map(int, f_i.readline().split())
    B2x, B2y, B2z = map(int, f_i.readline().split())
    B3x, B3y, B3z = map(int, f_i.readline().split())
    
    a = (B2x - B1x, B2y - B1y, B2z - B1z)
    b = (B3x - B1x, B3y - B1y, B3z - B1z)
    c = (Sx - Ex, Sy - Ey, Sz - Ez)
    
    detA = get_det(a, b, c)
    
    # the barrier looks like a line segment
    if detA == 0:
        print("HIT")
        return
    
    d = (Sx - B1x, Sy - B1y, Sz - B1z)
    
    s = get_det(d, b, c)
    t = get_det(a, d, c)
    u = get_det(a, b, d)
    if detA > 0:
        if s >= 0 and t >= 0 and s + t <= detA and 0 <= u <= detA:
            print("MISS")
        else:
            print("HIT")
    else:
        if s <= 0 and t <= 0 and s + t >= detA and detA <= u <= 0:
            print("MISS")
        else:
            print("HIT")

solve()

Submission status: Accepted

Solution code:
def det(a,b,c):
    return a[0]*b[1]*c[2] + a[2]*b[0]*c[1] + a[1]*b[2]*c[0] - a[2]*b[1]*c[0] - a[1]*b[0]*c[2] - a[0]*b[2]*c[1]

uaz = list(map(int, input().split()))
ene = list(map(int, input().split()))
br1 = list(map(int, input().split()))
br2 = list(map(int, input().split()))
br3 = list(map(int, input().split()))

edge1 = [br2[0] - br1[0], br2[1] - br1[1], br2[2] - br1[2]]
edge2 = [br3[0] - br1[0], br3[1] - br1[1], br3[2] - br1[2]]
ray   = [uaz[0] - ene[0], uaz[1] - ene[1], uaz[2] - ene[2]]
rhs   = [uaz[0] - br1[0], uaz[1] - br1[1], uaz[2] - br1[2]]

det_abc = det(edge1, edge2, ray)
if det_abc == 0:
    print("HIT")
else:
    u = det(rhs, edge2, ray)/det_abc
    v = det(edge1, rhs, ray)/det_abc
    t = det(edge1, edge2, rhs)/det_abc
    if 0.0 <= u <= 1.0 and 0.0 <= v <= 1.0 and u+v <= 1.0 and 0.0 < t <= 1.0:
        print("MISS")
    else:
        print("HIT")

Submission status: Runtime Error

Solution code:
def solve(A, b):
    for i in xrange(3):
        if A[i][i] == 0.0:
            for j in xrange(i+1, 3):
                if A[j][i]!=0.0:
                    A[i], A[j] = A[j], A[i]
                    b[i], b[j] = b[j], b[i]
        for j in xrange(3):
            if i==j:
                continue
            a = A[j][i] / A[i][i]
            for k in xrange(3):
                A[j][k] -= a * A[i][k]
            b[j] -= a * b[i]
    for i in xrange(3):
        b[i] /= A[i][i]
        A[i][i] /= A[i][i]

u = map(float, raw_input().split())
e = map(float, raw_input().split())
o = map(float, raw_input().split())
p = map(float, raw_input().split())
q = map(float, raw_input().split())
A = [[p[i]-o[i], q[i]-o[i], e[i]-u[i]] for i in xrange(3)]
b = [e[i] - o[i] for i in xrange(3)]
solve(A, b)
s, t, x = b
j = lambda x: -0.0000001 < x < 1.0000001
if j(s) and j(t) and j(s+t) and j(x):
    print "MISS"
else:
    print "HIT"

Submission status: Runtime Error

Solution code:
hdhafsdlqshflahsfhjs
afjahflka
fhajkfaslkdfa
fjajkfhajkh
djhfjaseafaf
xz

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math
import numpy as np

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def length(v):
    return math.sqrt(v[0] ** 2 + v[1] ** 2 + v[2] ** 2)

def dist(p0, p1):
    return math.sqrt( (p0[0] - p1[0]) ** 2 + (p0[1] - p1[1]) ** 2 + (p0[2] - p1[2]) ** 2)

# me
p0 = np.array(list(map(int, input().split())))

# enemy
p1 = np.array(list(map(int, input().split())))

# barrier
A = np.array(list(map(int, input().split())))
B = np.array(list(map(int, input().split())))
C = np.array(list(map(int, input().split())))

a = p1 - p0
b = A - B
c = A - C
d = A - p0

M = np.array([a, b, c]).T
tuv = np.linalg.solve(M, d)

t = tuv[0]
u = tuv[1]
v = tuv[2]

if 0 <= u <= 1 and 0 <= v <= 1 and 0 <= u + v <= 1:
    print('MISS')
else:
    print('HIT')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def det(a, b, c):
    return + a[0] * b[1] * c[2] \
           + a[2] * b[0] * c[1] \
           + a[1] * b[2] * c[0] \
           - a[2] * b[1] * c[0] \
           - a[1] * b[0] * c[2] \
           - a[0] * b[2] * c[1]

def sub(v0, v1):
    # v0 - v1
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])

# me
p0 = list(map(int, input().split()))

# enemy
p1 = list(map(int, input().split()))

# barrier
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a = sub(p1, p0)
b = sub(A, B)
c = sub(A, C)
d = sub(A, p0)

denom = det(a, b, c)
if denom > -0.0000001:
    t = det(d, b, c) / denom
    u = det(a, d, c) / denom
    v = det(a, b, d) / denom

    lower = -0.0000001
    upper = 1.0000001
    if lower <= u <= upper and lower <= v <= upper and lower <= u + v <= upper:
        print('MISS')
    else:
        print('HIT')
else:
    print('HIT')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def det(a, b, c):
    return + a[0] * b[1] * c[2] \
           + a[2] * b[0] * c[1] \
           + a[1] * b[2] * c[0] \
           - a[2] * b[1] * c[0] \
           - a[1] * b[0] * c[2] \
           - a[0] * b[2] * c[1]

def sub(v0, v1):
    # v0 - v1
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])

# me
p0 = list(map(int, input().split()))

# enemy
p1 = list(map(int, input().split()))

# barrier
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a = sub(p1, p0)
b = sub(A, B)
c = sub(A, C)
d = sub(A, p0)

denom = det(a, b, c)
lower = -0.0000001
upper = 1.0000001

if denom > lower:
    t = det(d, b, c) / denom
    u = det(a, d, c) / denom
    v = det(a, b, d) / denom

    if lower <= u <= upper and lower <= v <= upper and lower <= u + v <= upper:
        print('MISS')
    else:
        print('HIT')
else:
    print('HIT')

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

# refs
# https://shikousakugo.wordpress.com/2012/06/27/ray-intersection-2/

def det(a, b, c):
    return + a[0] * b[1] * c[2] \
           + a[2] * b[0] * c[1] \
           + a[1] * b[2] * c[0] \
           - a[2] * b[1] * c[0] \
           - a[1] * b[0] * c[2] \
           - a[0] * b[2] * c[1]

def sub(v0, v1):
    # v0 - v1
    return (v0[0] - v1[0], v0[1] - v1[1], v0[2] - v1[2])

# me
p0 = list(map(int, input().split()))

# enemy
p1 = list(map(int, input().split()))

# barrier
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

a = sub(p1, p0)
b = sub(A, B)
c = sub(A, C)
d = sub(A, p0)

EPS = 0.0000001
lower = -EPS
upper = 1 + EPS

denom = det(a, b, c)

if denom > lower:
    t = det(d, b, c) / denom
    u = det(a, d, c) / denom
    v = det(a, b, d) / denom

    # i am on barrier
    if -EPS < t < EPS:
        print('HIT')

    # barrier is not between ours
    elif t < 0:
        print('HIT')

    # hit barrier
    elif lower < t < upper and lower <= u <= upper and lower <= v <= upper and lower <= u + v <= upper:
        print('MISS')

    else:
        print('HIT')
else:
    print('HIT')

Submission status: Runtime Error

Solution code:
dot = lambda a,b:sum([a[i]*b[i] for i in range(3)])
cross = lambda a,b:[a[1]*b[2]-a[2]*b[1],a[2]*b[0]-a[0]*b[2],a[0]*b[1]-a[1]*b[0]]
m = lambda a,b:[a[i]-b[i] for i in range(3)]
l = lambda a:(a[0]**2+a[1]**2+a[2]**2)** 0.5
c = lambda a,b:[a*b[i] for i in range(3)]

def A():
  L=[list(map(int,input().split())) for i in range(5)]
  ab = m(L[1],L[0])
  L2 = [m(L[3],L[2]),m(L[4],L[3]),m(L[2],L[4])]
  n = cross(L2[0],L2[1])
  if dot(ab,n) == 0:
    return 'HIT'
  xa = m(L[0],L[2])
  xb = m(L[1],L[2])
  if dot(n,xa) * dot(n,xb) > 0:
    return 'HIT'
  da = abs(dot(n,xa))/l(n)
  db = abs(dot(n,xb))/l(n)
  a = da / (da + db)
  X = [c((1-a),xa)[i] + c(a,xb)[i] for i in range(3)]
  for i in range(1,4):
    if dot(n,cross(L2[i-1],m(X,L2[2+(i%3)]))) < 0:
      return 'MISS'
  return "HIT"
print(A())

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
from fractions import Fraction
import sys
if sys.version_info[0]>=3: raw_input=input

def gauss(a):
	if not a or len(a)==0: return None
	n=len(a)
	for i in range(n):
		if a[i][i]==0:
			for j in range(i+1,n):
				if a[j][i]!=0:
					for k in range(i,n+1): a[i][k]+=a[j][k]
					break
		for j in range(n):
			if i!=j:
				r = Fraction(a[j][i],a[i][i])
				for k in range(i,n+1): a[j][k] = a[j][k] - a[i][k]*r
	for i in range(n):
		x=Fraction(a[i][i],1)
		for j in range(len(a[i])):
			a[i][j] /= x
	return a

uaz=list(map(int,raw_input().split()))
enemy=[0]+[-x+y for x,y in zip(map(int,raw_input().split()),uaz)]
b0=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
b1=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
b2=[1]+[x-y for x,y in zip(map(int,raw_input().split()),uaz)]
sol=gauss(list(map(list,zip(b0,b1,b2,enemy,[1,0,0,0]))))
print('MISS' if sol and all(0<=e[-1]<=1 for e in sol) else 'HIT')