Problem:


牽牛と織女

織女は天帝の子供でしたが、父の言いつけであけてもくれても機を織っていました。

 織女の織る雲錦という見事な布で仕立てた服を着るのが天帝の楽しみでした。雲錦は寿命が短くすぐに劣化してしまいますが、働き者の織女が毎日織ってくれるので、問題はありませんでした。織女は、父の言いつけを守り、毎日毎日雲錦を織り続けていたので、ボーイフレンドはいませんでした。かわいそうに思った父は、天の川の向こう岸に住む牽牛という働き者を紹介し、嫁入りさせました。

 
すると、織女は、結婚の楽しさに夢中になって、機織りなどそっちのけで、牽牛と遊び呆けています。天帝のお気に入りの雲錦の服も新しく仕立てられないためボロボロになってしまいました。

 
これには父も怒って、織女を宮殿に連れ戻したいと思いました。しかし人間である牽牛の前にボロボロの服で姿を現すわけにはいきません。遊び呆けている二人を 3 角形の壁で遮断し自分以外の全てのものが行き来できなくすることを考えました。そして、牽牛に見つからずに、織女に会って、まじめに機を織るか、さもなければ強制的に連れ帰ると宣言するというのです。

天帝はこの作戦を遂行するために 3 角形の壁生成装置を開発することにしました。3 角形の 3 頂点の位置 (xp1, yp1), (xp2, yp2), (xp3, yp3)、牽牛の位置 (xk, yk)、および織女の位置 (xs, ys)、を入力とし、三角形が牽牛と織女を遮断しているか否かを判定し、遮断できている場合は OK、遮断できていない場合には NG を出力するプログラムを作成してください。ただし、遮断しているとは、牽牛と織女のいずれかが三角形の内側にあり、他方が外側にある場合を言います。牽牛と織女は三角形の頂点もしくは辺の上にはいないものとします。

織女と牽牛は時々刻々場所を変えるため、プログラムは様々な位置情報を入力し質問に答えなければなりません。

(xp1, yp1), (xp2, yp2), (xp3, yp3)、牽牛の位置 (xk, yk)、および織女の位置 (xs, ys)、を入力とし、三角形が牽牛と織女を遮断しているか否かを判定し、遮断できている場合は OK、遮断できていない場合には NG を出力するプログラムを作成してください。ただし、遮断しているとは、牽牛と織女のいずれかが三角形の内側にあり、他方が外側にある場合を言います。牽牛と織女は三角形の頂点もしくは辺の上にはいないものとします。

-->

Input

入力は以下の形式で与えられます。

n
query1
query2
:
queryn

１行目に判別したい情報の個数 n (n ≤ 10000)、続く n 行に i 番目の質問 queryi が与えられます。各質問は以下の形式で与えられます。

xp1 yp1 xp2 yp2 xp3 yp3 xk yk xs ys

各質問として、3 角形の 3 頂点の位置、牽牛の位置、および織女の位置 (-1000 ≤ xp1, yp1, xp2, yp2, xp3, yp3, xk, yk, xs, ys ≤ 1000) が１行に与えられます。入力はすべて整数です。

Output

質問ごとに、判定結果 OK または NG を１行に出力してください。

Sample Input

5
2 5 9 2 8 9 2 11 6 5
2 5 9 2 8 9 2 11 12 6
2 5 9 2 8 9 2 11 11 9
14 1 25 7 17 12 17 9 20 5
14 1 25 7 17 12 22 13 20 5

Output for the Sample Input

OK
NG
NG
NG
OK



Sample input:
5
2 5 9 2 8 9 2 11 6 5
2 5 9 2 8 9 2 11 12 6
2 5 9 2 8 9 2 11 11 9
14 1 25 7 17 12 17 9 20 5
14 1 25 7 17 12 22 13 20 5


Sample output:
OK
NG
NG
NG
OK

Submission status: Wrong Answer

Solution code:
def isin(x,y):
    if S(x1,y1,x2,y2,x,y)+S(x1,y1,x3,y3,x,y)+S(x3,y3,x2,y2,x,y)-S(x1,y1,x2,y2,x3,y3) != 0:
        return False
    else:
        return True

def S(x1,y1,x2,y2,x3,y3):
    return abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))

for roop in range(int(raw_input())):
    x1,y1,x2,y2,x3,y3,xk,yk,xs,ys = map(int,raw_input().split())
    print "OK" if isin(xk,yk) != isin(xs,ys) else "NO"

Submission status: Wrong Answer

Solution code:
from operator import sub,mul
def cross(a,b):
    return a[0]*b[1] - a[1]*b[0]

def func(a,b):##
    return [map(sub,aa,bb) for aa,bb in zip(a,b)]

for _ in xrange(input()):
    line = map(int,raw_input().split())
    tmp = zip(line[:6:2],line[1:6:2])
    v = func(tmp,tmp[1:]+[tmp[0]])
    f = func(tmp,[line[6:8]]*3)
    m = func(tmp,[line[8:]]*3)    
    if reduce(mul,map(cross,v,f)) * reduce(mul,map(cross,v,m)) < 0:
        print "OK"
    else:
        print "NG"

Submission status: Wrong Answer

Solution code:
from operator import sub,mul
def cross(a,b):
    return a[0]*b[1] - a[1]*b[0]

def func(a,b):#
    return [map(sub,aa,bb) for aa,bb in zip(a,b)]

for _ in xrange(input()):
    line = map(int,raw_input().split())
    tmp = zip(line[:6:2],line[1:6:2])
    v = func(tmp[1:]+[tmp[0]],tmp)
    m = func([line[6:8]]*3,tmp)
    f = func([line[8:]]*3,tmp) 
    if reduce(mul,map(cross,v,f)) * reduce(mul,map(cross,v,m)) < 0:
        print "OK"
    else:
        print "NG"

Submission status: Wrong Answer

Solution code:
from operator import sub,mul
def cross(a,b):
    return a[0]*b[1] - a[1]*b[0]

def func(a,b):#
    return [map(sub,aa,bb) for aa,bb in zip(a,b)]

for _ in xrange(input()):
    line = map(int,raw_input().split())
    tmp = zip(line[:6:2],line[1:6:2])
    v = func(tmp[1:]+[tmp[0]],tmp)
    m = func([line[6:8]]*3,tmp)
    f = func([line[8:]]*3,tmp) 
    if len(filter(lambda x:x<0,map(cross,v,m))) == \
            len(filter(lambda x:x<0,map(cross,v,f))):
        print "NG"
    else:
        print "OK"

Submission status: Wrong Answer

Solution code:
from operator import sub,mul
def cross(a,b):
    return a[0]*b[1] - a[1]*b[0]

def func(a,b):#
    return [map(sub,aa,bb) for aa,bb in zip(a,b)]

def check(a):
    return all(map(lambda x:x<0,a)) or all(map(lambda x:x>0,a))

for _ in xrange(input()):
    line = map(int,raw_input().split())
    tmp = zip(line[:6:2],line[1:6:2])
    v = func(tmp[1:]+[tmp[0]],tmp)
    m = func([line[6:8]]*3,tmp)
    f = func([line[8:]]*3,tmp) 
    if check(map(cross,m,v)) != check(map(cross,f,v)):
        print "OK"
    else:
        print "NA"

Submission status: Accepted

Solution code:
def isin(x,y):
    if S(x1,y1,x2,y2,x,y)+S(x1,y1,x3,y3,x,y)+S(x3,y3,x2,y2,x,y)-S(x1,y1,x2,y2,x3,y3) != 0:
        return False
    else:
        return True

def S(x1,y1,x2,y2,x3,y3):
    return abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))

for roop in range(int(raw_input())):
    x1,y1,x2,y2,x3,y3,xk,yk,xs,ys = map(int,raw_input().split())
    print "OK" if isin(xk,yk) != isin(xs,ys) else "NG"

Submission status: Accepted

Solution code:
def side(a, b, c):
  return (c[1]-a[1])*(b[0]-a[0])-(b[1]-a[1])*(c[0]-a[0])>0
def isInner(x): return (side(p0, p1, x)==side(p1, p2, x)==side(p2, p0, x))

for _ in [0]*input():
  P = map(int, raw_input().split())
  p0 = P[0:2]
  p1 = P[2:4]
  p2 = P[4:6]
  x1 = P[6:8]
  x2 = P[8:]
  print ['NG','OK'][isInner(x1)!=isInner(x2)]

Submission status: Accepted

Solution code:
def side(a, b, c):
  return (c[1]-a[1])*(b[0]-a[0])-(b[1]-a[1])*(c[0]-a[0])>0
def isIn(x):
  return (side(p0, p1, x)==side(p1, p2, x)==side(p2, p0, x))

for _ in [0]*input():
  P = map(int, raw_input().split())
  p0 = P[0:2]
  p1 = P[2:4]
  p2 = P[4:6]
  print ['NG','OK'][isIn(P[6:8])!=isIn(P[8:])]

Submission status: Accepted

Solution code:
def out_p(bx, by, x0, y0, x1, y1):
    a, b = x0-bx, y0-by
    c, d = x1-bx, y1-by
    return a*d - b*c
def sgn(x):
    return -1 if x<0 else 1
n = input()
xp = [0] * 3; yp = [0] * 3;
xk, yk, xs, ys = [0]*4
for i in xrange(n):
    xp[0], yp[0], xp[1], yp[1], xp[2], yp[2], xk, yk, xs, ys = map(int, raw_input().split())
    rk = [0]*3
    for i in xrange(3):
        rk[i] = sgn(out_p(xp[i], yp[i], xp[i-2], yp[i-2], xk, yk))
    k_in = (rk[0] == rk[1] == rk[2])
    rs = [0]*3
    for i in xrange(3):
        rs[i] = sgn(out_p(xp[i], yp[i], xp[i-2], yp[i-2], xs, ys))
    s_in = (rs[0] == rs[1] == rs[2])
    print "OK" if k_in ^ s_in else "NG"

Submission status: Accepted

Solution code:
EPS=1e-10
def crossP(aa,bb,cc,dd):
    a = (bb-aa).real
    b = (cc-dd).real
    c = (bb-aa).imag
    d = (cc-dd).imag
    e = (cc-aa).real
    f = (cc-aa).imag
    det = a*d - b*c
    if abs(det) <EPS:
        return(-9999+(-9999)*1j)
    x = (d*e-b*f)/det
    y = (-c*e+a*f)/det
    return(x+y*1j)

def rangeP(st):
    return((0.0<=st.real<=1.0) and (0.0<=st.imag<=1.0))

if __name__ == '__main__':
	n = int(input().strip())
	for i in range(n):
	    [xp1,yp1,xp2,yp2,xp3,yp3,xk,yk,xs,ys] = map(int, input().strip().split())
	    a = xp1+yp1*1j
	    b = xp2+yp2*1j
	    c = xp3+yp3*1j
	    k = xk+yk*1j
	    s = xs+ys*1j
	    shut = 0
	    if rangeP(crossP(a,b,k,s)):
	        shut += 1
	    if rangeP(crossP(b,c,k,s)):
	        shut += 1
	    if rangeP(crossP(c,a,k,s)):
	        shut += 1
	    if shut == 1:
	        print("OK")
	    else:
	        print("NG")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0143

"""
import sys
from sys import stdin
input = stdin.readline
from math import sqrt, atan2, acos, sin, cos


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        return Point(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Point(self.x / other, self.y / other)

    def __lt__(self, other):
        if self.x == other.x:
            return self.y < other.y
        else:
            return self.x < other.x

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

    def norm(self):
        return self.x * self.x + self.y * self.y

    def __abs__(self):
        return sqrt(self.norm())

    def ccw(self, p0, p1):
        # ??????2???(p0, p1)?????????????????????????????????????????¢????????????
        a = Vector(p1 - p0)
        b = Vector(self - p0)
        if Vector.cross(a, b) > Point.epsilon:
            return 1 # 'COUNTER_CLOCKWISE'
        elif Vector.cross(a, b) < -Point.epsilon:
            return -1 # 'CLOCKWISE'
        elif Vector.dot(a, b) < -Point.epsilon:
            return 2 # 'ONLINE_BACK'
        elif a.norm() < b.norm():
            return -2 # 'ONLINE_FRONT'
        else:
            return 0 # 'ON_SEGMENT'

    def project(self, s):
        # ??????(Point)????????????s??????????????????????????????????????§?¨?(?°???±)????±???????
        base = Vector(s.p2 - s.p1)
        a = Vector(self - s.p1)
        r = Vector.dot(a, base)
        r /= base.norm()
        return s.p1 + base * r

    def reflect(self, s):
        # ??????s???????§°?????¨?????????????????¨???????§°??????????????§?¨?(????°?)????±???????
        proj = self.project(s)
        return self + (proj - self)*2

    def distance(self, s):
        # ????????¨??????s????????¢????¨??????????
        if Vector.dot(s.p2-s.p1, self-s.p1) < 0.0:
            return abs(self - s.p1)
        if Vector.dot(s.p1-s.p2, self-s.p2) < 0.0:
            return abs(self - s.p2)
        return abs(Vector.cross(s.p2-s.p1, self-s.p1) / abs(s.p2-s.p1))


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        return Vector(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Vector(self.x / other, self.y / other)

    @classmethod
    def dot(cls, a, b):
        return a.x * b.x + a.y * b.y

    @classmethod
    def cross(cls, a, b):
        return a.x * b.y - a.y * b.x

    @classmethod
    def is_orthogonal(cls, a, b):
        return abs(Vector.dot(a, b)) < Vector.epsilon

    @classmethod
    def is_parallel(cls, a, b):
        return abs(Vector.cross(a, b)) < Vector.epsilon


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    def intersect(self, s):
        # ????????¨??????????????????????????????????????????????????????
        ans1 = s.p1.ccw(self.p1, self.p2) * s.p2.ccw(self.p1, self.p2)
        ans2 = self.p1.ccw(s.p1, s.p2) * self.p2.ccw(s.p1, s.p2)
        return ans1 <= 0 and ans2 <= 0

    def cross_point(self, s):
        # ????????¨??????????????????????????????????????§?¨?????±???????
        base = s.p2 - s.p1
        d1 = abs(Vector.cross(base, self.p1-s.p1))
        d2 = abs(Vector.cross(base, self.p2-s.p1))
        t = d1 / (d1 + d2)
        return self.p1 + (self.p2 - self.p1) * t

    def distance(self, s):
        # ????????¨?????????????????????????????¢????±???????
        if self.intersect(s):
            return 0.0
        d1 = s.p1.distance(self)
        d2 = s.p2.distance(self)
        d3 = self.p1.distance(s)
        d4 = self.p2.distance(s)
        return min(d1, d2, d3, d4)


    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, x, y=Point(), r=1.0):
        if isinstance(x, Point):
            self.c = x
            self.r = y
        elif isinstance(x, tuple):
            self.c = Point(x[0], x[1])
            self.r = r

    def cross_points(self, s):
        if isinstance(s, Segment):
            pr = self.c.project(s)
            e = (s.p2 - s.p1) / abs(s.p2 - s.p1)
            base = sqrt(self.r * self.r - (pr - self.c).norm())
            return pr + e * base, pr - e * base
        elif isinstance(s, Cirle):
            c2 = s
            d = abs(self.c - c2.c)
            a = acos((self.r * self.r + d * d - c2.r * c2.r) / (2 * self.r * d))
            t = atan2(c2.c.y - self.c.y, c2.c.x - self.c.x)
            temp1 = Point(cos(t+a)*self.r, sin(t+a)*self.r)
            temp2 = Point(cos(t-a)*self.r, sin(t-a)*self.r)
            return self.c + temp1, self.c + temp2

class Triangle(object):
    def __init__(self, p1, p2, p3):
        self.p1 = p1
        self.p2 = p2
        self.p3 = p3

    def length(self):
        # 3????????????
        l1 = hypot(self.p1.x-self.p2.x, self.p1.y-self.p2.y)
        l2 = hypot(self.p2.x-self.p3.x, self.p2.y-self.p3.y)
        l3 = hypot(self.p3.x-self.p1.x, self.p3.y-self.p1.y)
        return l1, l2, l3

    def area(self):
        # ????§???¢?????¢???
        a, b, c = self.length()
        z = (a+b+c) / 2.0
        return sqrt(z * (z-a)*(z-b)*(z-c))

    def is_inside(self, p):
        # ???p?????????????§???¢????????´?????????????????????
        t1 = p.ccw(self.p1, self.p2)
        t2 = p.ccw(self.p2, self.p3)
        t3 = p.ccw(self.p3, self.p1)
        if (t1 < 0 and t2 < 0 and t3 < 0) or t1 > 0 and t2 > 0 and t3 > 0:
            return True
        else:
            return False


def main(args):
    n = int(input())
    for _ in range(n):
        xp1, yp1, xp2, yp2, xp3, yp3, xk, yk, xs, ys = map(int, input().split())
        t = Triangle(Point(xp1, yp1), Point(xp2, yp2), Point(xp3, yp3))
        pk = Point(xk, yk)
        ps = Point(xs, ys)
        result_k = t.is_inside(pk)
        result_s = t.is_inside(ps)
        if result_k != result_s:
            print('OK')
        else:
            print('NG')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0143

"""
import sys
from sys import stdin
input = stdin.readline
from math import sqrt, atan2, acos, sin, cos


class Point(object):
    epsilon = 1e-10

    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        return Point(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Point(self.x / other, self.y / other)

    def __lt__(self, other):
        if self.x == other.x:
            return self.y < other.y
        else:
            return self.x < other.x

    def __eq__(self, other):
        from math import fabs
        if fabs(self.x - other.x) < Point.epsilon and fabs(self.y - other.y) < Point.epsilon:
            return True
        else:
            return False

    def norm(self):
        return self.x * self.x + self.y * self.y

    def __abs__(self):
        return sqrt(self.norm())

    def ccw(self, p0, p1):
        # ??????2???(p0, p1)?????????????????????????????????????????¢????????????
        a = Vector(p1 - p0)
        b = Vector(self - p0)
        if Vector.cross(a, b) > Point.epsilon:
            return 1 # 'COUNTER_CLOCKWISE'
        elif Vector.cross(a, b) < -Point.epsilon:
            return -1 # 'CLOCKWISE'
        elif Vector.dot(a, b) < -Point.epsilon:
            return 2 # 'ONLINE_BACK'
        elif a.norm() < b.norm():
            return -2 # 'ONLINE_FRONT'
        else:
            return 0 # 'ON_SEGMENT'

    def project(self, s):
        # ??????(Point)????????????s??????????????????????????????????????§?¨?(?°???±)????±???????
        base = Vector(s.p2 - s.p1)
        a = Vector(self - s.p1)
        r = Vector.dot(a, base)
        r /= base.norm()
        return s.p1 + base * r

    def reflect(self, s):
        # ??????s???????§°?????¨?????????????????¨???????§°??????????????§?¨?(????°?)????±???????
        proj = self.project(s)
        return self + (proj - self)*2

    def distance(self, s):
        # ????????¨??????s????????¢????¨??????????
        if Vector.dot(s.p2-s.p1, self-s.p1) < 0.0:
            return abs(self - s.p1)
        if Vector.dot(s.p1-s.p2, self-s.p2) < 0.0:
            return abs(self - s.p2)
        return abs(Vector.cross(s.p2-s.p1, self-s.p1) / abs(s.p2-s.p1))


class Vector(Point):
    def __init__(self, x=0.0, y=0.0):
        if isinstance(x, tuple):
            self.x = x[0]
            self.y = x[1]
        elif isinstance(x, Point):
            self.x = x.x
            self.y = x.y
        else:
            self.x = x
            self.y = y

    # ????????????
    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    def __mul__(self, other):
        return Vector(other * self.x, other * self.y)

    def __truediv__(self, other):
        return Vector(self.x / other, self.y / other)

    @classmethod
    def dot(cls, a, b):
        return a.x * b.x + a.y * b.y

    @classmethod
    def cross(cls, a, b):
        return a.x * b.y - a.y * b.x

    @classmethod
    def is_orthogonal(cls, a, b):
        return abs(Vector.dot(a, b)) < Vector.epsilon

    @classmethod
    def is_parallel(cls, a, b):
        return abs(Vector.cross(a, b)) < Vector.epsilon


class Segment(object):
    def __init__(self, p1=Point(), p2=Point()):
        if isinstance(p1, Point):
            self.p1 = p1
            self.p2 = p2
        elif isinstance(p1, tuple):
            self.p1 = Point(p1[0], p1[1])
            self.p2 = Point(p2[0], p2[1])

    def intersect(self, s):
        # ????????¨??????????????????????????????????????????????????????
        ans1 = s.p1.ccw(self.p1, self.p2) * s.p2.ccw(self.p1, self.p2)
        ans2 = self.p1.ccw(s.p1, s.p2) * self.p2.ccw(s.p1, s.p2)
        return ans1 <= 0 and ans2 <= 0

    def cross_point(self, s):
        # ????????¨??????????????????????????????????????§?¨?????±???????
        base = s.p2 - s.p1
        d1 = abs(Vector.cross(base, self.p1-s.p1))
        d2 = abs(Vector.cross(base, self.p2-s.p1))
        t = d1 / (d1 + d2)
        return self.p1 + (self.p2 - self.p1) * t

    def distance(self, s):
        # ????????¨?????????????????????????????¢????±???????
        if self.intersect(s):
            return 0.0
        d1 = s.p1.distance(self)
        d2 = s.p2.distance(self)
        d3 = self.p1.distance(s)
        d4 = self.p2.distance(s)
        return min(d1, d2, d3, d4)


    @classmethod
    def is_orthogonal(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_orthogonal(a, b)

    @classmethod
    def is_parallel(cls, s1, s2):
        a = Vector(s1.p2 - s1.p1)
        b = Vector(s2.p2 - s2.p1)
        return Vector.is_parallel(a, b)


class Line(Segment):
    pass


class Cirle(object):
    def __init__(self, x, y=Point(), r=1.0):
        if isinstance(x, Point):
            self.c = x
            self.r = y
        elif isinstance(x, tuple):
            self.c = Point(x[0], x[1])
            self.r = r

    def cross_points(self, s):
        if isinstance(s, Segment):
            pr = self.c.project(s)
            e = (s.p2 - s.p1) / abs(s.p2 - s.p1)
            base = sqrt(self.r * self.r - (pr - self.c).norm())
            return pr + e * base, pr - e * base
        elif isinstance(s, Cirle):
            c2 = s
            d = abs(self.c - c2.c)
            a = acos((self.r * self.r + d * d - c2.r * c2.r) / (2 * self.r * d))
            t = atan2(c2.c.y - self.c.y, c2.c.x - self.c.x)
            temp1 = Point(cos(t+a)*self.r, sin(t+a)*self.r)
            temp2 = Point(cos(t-a)*self.r, sin(t-a)*self.r)
            return self.c + temp1, self.c + temp2

class Triangle(object):
    def __init__(self, p1, p2, p3):
        self.p1 = p1
        self.p2 = p2
        self.p3 = p3

    def length(self):
        # 3????????????
        l1 = hypot(self.p1.x-self.p2.x, self.p1.y-self.p2.y)
        l2 = hypot(self.p2.x-self.p3.x, self.p2.y-self.p3.y)
        l3 = hypot(self.p3.x-self.p1.x, self.p3.y-self.p1.y)
        return l1, l2, l3

    def area(self):
        # ????§???¢?????¢???
        a, b, c = self.length()
        z = (a+b+c) / 2.0
        return sqrt(z * (z-a)*(z-b)*(z-c))

    def is_inside(self, p):
        # ???p?????????????§???¢????????´?????????????????????
        t1 = p.ccw(self.p1, self.p2)
        t2 = p.ccw(self.p2, self.p3)
        t3 = p.ccw(self.p3, self.p1)
        if (t1 < 0 and t2 < 0 and t3 < 0) or (t1 > 0 and t2 > 0 and t3 > 0):
            return True
        else:
            return False


def main(args):
    n = int(input())
    for _ in range(n):
        xp1, yp1, xp2, yp2, xp3, yp3, xk, yk, xs, ys = map(int, input().split())
        t = Triangle(Point(xp1, yp1), Point(xp2, yp2), Point(xp3, yp3))
        pk = Point(xk, yk)
        ps = Point(xs, ys)
        result_k = t.is_inside(pk)
        result_s = t.is_inside(ps)
        if result_k != result_s:
            print('OK')
        else:
            print('NG')


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
class Vector:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    @staticmethod
    def cross_product(point1, point2):
        return point1.x * point2.y - point1.y * point2.x


class Triangle:
    def __init__(self, x1, y1, x2, y2, x3, y3):
        self.point1 = Vector(x1, y1)
        self.point2 = Vector(x2, y2)
        self.point3 = Vector(x3, y3)

    def is_contain(self, point):
        line1 = point - self.point1
        line2 = self.point2 - self.point1
        direct1 = Vector.cross_product(line1, line2)

        line1 = point - self.point2
        line2 = self.point3 - self.point2
        direct2 = Vector.cross_product(line1, line2)

        line1 = point - self.point3
        line2 = self.point1 - self.point3
        direct3 = Vector.cross_product(line1, line2)

        if 0 < direct1 and 0 < direct2 and 0 < direct3:
            return 1
        elif direct1 < 0 and direct2 < 0 and direct3 < 0:
            return 1
        else:
            return -1


for _ in range(int(input())):
    data = [int(item) for item in input().split(" ")]

    triangle = Triangle(data[0], data[1], data[2], data[3], data[4], data[5])
    altair_point = Vector(data[6], data[7])
    vega_point = Vector(data[8], data[9])

    is_contain1 = triangle.is_contain(altair_point)
    is_contain2 = triangle.is_contain(vega_point)
    result = is_contain1 * is_contain2

    if result == -1:
        print("OK")
    else:
        print("NG")

Submission status: Accepted

Solution code:
# AOJ 0143 Altair and Vega
# Python3 2018.6.18 bal4u

# a, b, はラインの同一側にあるか
def is_atSameSide(a, b, line):
	sa = (line[1].real-line[0].real)*(a.imag-line[0].imag) \
		 + (line[1].imag-line[0].imag)*(line[0].real-a.real);
	sb = (line[1].real-line[0].real)*(b.imag-line[0].imag) \
		 + (line[1].imag-line[0].imag)*(line[0].real-b.real);
	return (sa > 0 and sb > 0) or (sa < 0 and sb < 0)    # a, b at same side

for i in range(int(input())):
	buf = list(map(int, input().split()))
	p1 = complex(buf[0], buf[1])
	p2 = complex(buf[2], buf[3])
	p3 = complex(buf[4], buf[5])
	pk = complex(buf[6], buf[7])
	ps = complex(buf[8], buf[9])

	kin = is_atSameSide(p3, pk, [p1, p2]) & \
		  is_atSameSide(p1, pk, [p2, p3]) & \
		  is_atSameSide(p2, pk, [p3, p1])
	sin = is_atSameSide(p3, ps, [p1, p2]) & \
		  is_atSameSide(p1, ps, [p2, p3]) & \
		  is_atSameSide(p2, ps, [p3, p1])
	print("OK" if kin ^ sin else "NG")

Submission status: Accepted

Solution code:
from collections import namedtuple
Vector=namedtuple("Vector","x y")

def square(a,b,c):
    return abs((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y))

n=input()
for i in range(n):
    xp1,yp1,xp2,yp2,xp3,yp3,xk,yk,xs,ys=map(int,raw_input().split())
    A=Vector(x=xp1, y=yp1)
    B=Vector(x=xp2, y=yp2)
    C=Vector(x=xp3, y=yp3)
    K=Vector(x=xk, y=yk)
    S=Vector(x=xs, y=ys)
    ABC=square(A,B,C)
    ABCK=square(A,B,K)+square(A,K,C)+square(K,B,C)
    ABCS=square(A,B,S)+square(A,S,C)+square(S,B,C)
    print "NG" if (ABC==ABCK)==(ABC==ABCS) else	"OK"

Submission status: Accepted

Solution code:
from operator import sub,mul
def cross(a,b):
    return a[0]*b[1] - a[1]*b[0]

def func(a,b):#
    return [map(sub,aa,bb) for aa,bb in zip(a,b)]

def check(a):
    return all(map(lambda x:x<0,a)) or all(map(lambda x:x>0,a))

for _ in xrange(input()):
    line = map(int,raw_input().split())
    tmp = zip(line[:6:2],line[1:6:2])
    v = func(tmp[1:]+[tmp[0]],tmp)
    m = func([line[6:8]]*3,tmp)
    f = func([line[8:]]*3,tmp) 
    if check(map(cross,m,v)) != check(map(cross,f,v)):
        print "OK"
    else:
        print "NG"

Submission status: Accepted

Solution code:
def sign(p1, p2, p3):
    return (p1[0] - p3[0]) * (p2[1] - p3[1]) - (p2[0] - p3[0]) * (p1[1] - p3[1])


def check(triangle, pt):
    v1 = [triangle[0], triangle[1]]
    v2 = [triangle[2], triangle[3]]
    v3 = [triangle[4], triangle[5]]

    b1 = sign(pt, v1, v2)
    if b1 > 0:
        flag1 = 1
    else:
        flag1 = 0

    b2 = sign(pt, v2, v3)
    if b2 > 0:
        flag2 = 1
    else:
        flag2 = 0

    b3 = sign(pt, v3, v1)
    if b3 > 0:
        flag3 = 1
    else:
        flag3 = 0

    return ((flag1 == flag2) and (flag2 == flag3))


n = int(input())

for _ in range(n):
    query = list(map(int, input().split()))
    triangle = query[0:6]
    hikoboshi = query[6:8]
    orihime = query[8:10]

    check1 = check(triangle, hikoboshi)
    check2 = check(triangle, orihime)
    if check1 == check2:
        print("NG")
    else:
        print("OK")

Submission status: Runtime Error

Solution code:
import numpy as np
def crossP(a, b, c, d):
    e = b - a
    f = c - d
    g = c - a
    A = np.matrix([[e.real,f.real],[e.imag, f.imag]])
    B = np.matrix([[g.real],[g.imag]])
    try:
        C = np.linalg.solve(A, B)
    except:
        return(-9999+(-9999)*1j)
    return(C[0,0]+C[1,0]*1j)

def rangeP(st):
    return((0.0<=st.real<=1.0) and (0.0<=st.imag<=1.0))

if __name__ == '__main__':
	n = int(input().strip())
	for i in range(n):
	    [xp1,yp1,xp2,yp2,xp3,yp3,xk,yk,xs,ys] = map(int, input().strip().split())
	    a = xp1+yp1*1j
	    b = xp2+yp2*1j
	    c = xp3+yp3*1j
	    k = xk+yk*1j
	    s = xs+ys*1j
	    shut = 0
	    if rangeP(crossP(a,b,k,s)):
	        shut += 1
	    if rangeP(crossP(b,c,k,s)):
	        shut += 1
	    if rangeP(crossP(c,a,k,s)):
	        shut += 1
	    if shut == 1:
	        print("OK")
	    else:
	        print("NG")