Problem:


投石おみくじ

 「自分の道は自分で切り開く」をモットーに、ある神社が自分自身の手で運勢を決めるおみくじを作りました。そのおみくじを引く人にはまず6つの石を投げてもらい、その投げた石の一つ目と二つ目を結ぶ 線分、三つ目と四つ目を結ぶ 線分、五つ目と六つ目を結ぶ 線分の3本の線分の交点を頂点とする 三角形の面積から運勢を決めるというものです。各運勢と三角形の面積との関係は以下のとおりです。

線分の交点を頂点とする三角形の面積            運勢

         1,900,000以上     大吉 (dai-kichi)

 
 1,000,000以上1,900,000未満 中吉 (chu-kichi)

 
  100,000以上1,000,000未満    吉 (kichi)

 
   0より大きく 100,000未満     小吉 (syo-kichi)

 
          三角形なし            凶 (kyo)

 しかし、三角形の面積の大きさの判定は神主さんが手計算でやっているので正確とはいえず、時間もかかってしまいます。そこで近所に住む優秀なプログラマであるあなたは、一刻でも早くプログラムを書いて神主さんを助けてあげることにしました。

 3 本の線分の情報を入力とし、線分の交点を頂点とする 三角形の面積から運勢を出力するプログラムを作成してください。線分の情報は始点の座標 (x1, y1) と、終点の座標 (x2, y2) が与えられ、始点と終点の座標は必ず異なることとします。また、2 つ以上の線分が同一直線上にある場合、交点を持たない 2 つの線分がある場合、3 つの線分が 1 点で交わる場合は、「三角形なし」となります。

Input

 複数のデータセットの並びが入力として与えられます。入力の終わりはゼロ4つの行で示されます。
 各データセットは以下の形式で与えられます。

line1
line2
line3

i 行目に i 番目の線分の情報が与えられます。各線分の情報は以下の形式で与えられます。

x1 y1 x2 y2

線分の端点の座標を表す整数 (x1, y1),  (x2, y2) (-1000 ≤ x1, y1, x2, y2 ≤ 1000 ) が空白区切りで与えられます。

Output

データセット毎に、おみくじの結果を１行に出力します。

Sample Input

-3 -2 9 6
3 -2 7 6
-1 0 5 0
2 2 -1 -1
0 1 2 1
-3 -1 3 1
0 0 0 0

Output for the Sample Input

syo-kichi
kyo



Sample input:
-3 -2 9 6
3 -2 7 6
-1 0 5 0
2 2 -1 -1
0 1 2 1
-3 -1 3 1
0 0 0 0


Sample output:
syo-kichi
kyo

Submission status: Wrong Answer

Solution code:
def denomi(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    return (by-ay)*(dx-cx)-(bx-ax)*(dy-cy)
    
def getip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = denomi(xy1,xy2)*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y
 
def ison(x,y,xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    if min(cx,dx) <= x <= max(cx,dx) and min(cy,dy) <= y <= max(cy,dy):
            if min(ax,bx) <= x <= max(ax,bx) and min(ay,by) <= y <= max(ay,by):
                return True
    return False

while 1:
    xy1 = map(int,raw_input().split())
    if xy1.count(0) == 4: break
    xy2 = map(int,raw_input().split())
    xy3 = map(int,raw_input().split())
    if denomi(xy1,xy2) != 0 and denomi(xy2,xy3) != 0 and denomi(xy3,xy1) != 0:
        x1,y1 = getip(xy1,xy2)
        x2,y2 = getip(xy2,xy3)
        x3,y3 = getip(xy3,xy1)
    if ison(x1,y1,xy1,xy2) and ison(x2,y2,xy2,xy3) and ison(x3,y3,xy3,xy1):
        S = abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0
        if   S >= 1900000: print "dai-kichi"
        elif S >= 1000000: print "chu-kichi"
        elif S >= 100000 : print "kichi"
        else             : print "syo-kichi"
    else:
        print "kyo"

Submission status: Wrong Answer

Solution code:
def denomi(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    return (by-ay)*(dx-cx)-(bx-ax)*(dy-cy)
    
def getip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = denomi(xy1,xy2)*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y
 
def ison(x,y,xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    if min(cx,dx) <= x <= max(cx,dx) and min(cy,dy) <= y <= max(cy,dy):
            if min(ax,bx) <= x <= max(ax,bx) and min(ay,by) <= y <= max(ay,by):
                return True
    return False

while 1:
    xy1 = map(int,raw_input().split())
    if xy1.count(0) == 4: break
    xy2 = map(int,raw_input().split())
    xy3 = map(int,raw_input().split())
    if denomi(xy1,xy2) != 0 and denomi(xy2,xy3) != 0 and denomi(xy3,xy1) != 0:
        x1,y1 = getip(xy1,xy2)
        x2,y2 = getip(xy2,xy3)
        x3,y3 = getip(xy3,xy1)
        if ison(x1,y1,xy1,xy2) and ison(x2,y2,xy2,xy3) and ison(x3,y3,xy3,xy1):
            S = abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0
            if   S >= 1900000: print "dai-kichi"
            elif S >= 1000000: print "chu-kichi"
            elif S >= 100000 : print "kichi"
            else             : print "syo-kichi"
        else:
            print "kyo"
    else:
        print "kyo"

Submission status: Wrong Answer

Solution code:
def iscross(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx)
    td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx)
    return tc*td < 0
    
def getip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = ((by-ay)*(dx-cx)-(bx-ax)*(dy-cy))*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y

while 1:
    xy1 = map(int,raw_input().split())
    if xy1.count(0) == 4: break
    xy2 = map(int,raw_input().split())
    xy3 = map(int,raw_input().split())
    if iscross(xy1,xy2) and iscross(xy2,xy3) and iscross(xy3,xy1):
        x1,y1 = getip(xy1,xy2)
        x2,y2 = getip(xy2,xy3)
        x3,y3 = getip(xy3,xy1)
        S = abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0
        if   S >= 1900000: print "dai-kichi"
        elif S >= 1000000: print "chu-kichi"
        elif S >= 100000 : print "kichi"
        else             : print "syo-kichi"
    else:
        print "kyo"

Submission status: Wrong Answer

Solution code:
def isX(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx)
    td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx)
    return tc*td < 0
    
def ip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = ((by-ay)*(dx-cx)-(bx-ax)*(dy-cy))*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y

while 1:
    xy1 = map(int,raw_input().split())
    if xy1.count(0) == 4: break
    xy2 = map(int,raw_input().split())
    xy3 = map(int,raw_input().split())
    if isX(xy1,xy2) and isX(xy2,xy3) and isX(xy3,xy1):
        x1,y1 = ip(xy1,xy2); x2,y2 = ip(xy2,xy3); x3,y3 = ip(xy3,xy1)
        S = abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))
        if   S >= 1900000*2: print "dai-kichi"
        elif S >= 1000000*2: print "chu-kichi"
        elif S >= 100000*2 : print "kichi"
        else               : print "syo-kichi"
    else:
        print "kyo"

Submission status: Accepted

Solution code:
def isX(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx)
    td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx)
    return tc*td < 0
    
def ip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = ((by-ay)*(dx-cx)-(bx-ax)*(dy-cy))*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y

while 1:
    xy1 = map(int,raw_input().split())
    if xy1.count(0) == 4: break
    xy2 = map(int,raw_input().split())
    xy3 = map(int,raw_input().split())
    if isX(xy1,xy2) and isX(xy2,xy3) and isX(xy3,xy1):
        x1,y1 = ip(xy1,xy2); x2,y2 = ip(xy2,xy3); x3,y3 = ip(xy3,xy1)
        S = abs(x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2))/2.0
        if   S >= 1900000: print "dai-kichi"
        elif S >= 1000000: print "chu-kichi"
        elif S >= 100000 : print "kichi"
        elif S > 0       : print "syo-kichi"
        else             : print "kyo"
    else:
        print "kyo"

Submission status: Accepted

Solution code:
# Aizu Problem 0187: Stoning Fortune
#
import sys, math, os, bisect

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

def on_segment(p, q, r):
    # Given three colinear points p, q, r, the function checks if
    # point q lies on line segment 'pr'
    return q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and \
           q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])

def orientation(p, q, r):
    # To find orientation of ordered triplet (p, q, r).
    # The function returns following values
    #   0 --> p, q and r are colinear
    #   1 --> Clockwise
    #   2 --> Counterclockwise
    val = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
    if val == 0:
        return 0
    return 1 if val > 0 else 2


def do_intersect(p1, q1, p2, q2):
    # The main function that returns true if line segment 'p1q1'
    # and 'p2q2' intersect.
    o1 = orientation(p1, q1, p2)
    o2 = orientation(p1, q1, q2)
    o3 = orientation(p2, q2, p1)
    o4 = orientation(p2, q2, q1)
    #
    # General case:
    if o1 != o2 and o3 != o4:
        return True
    #
    # Special Cases:
    # 
    # p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if o1 == 0 and on_segment(p1, p2, q1):
        return True
    # p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if o2 == 0 and on_segment(p1, q2, q1):
        return True
    # p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if o3 == 0 and on_segment(p2, p1, q2):
        return True
    #  p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if o4 == 0 and on_segment(p2, q1, q2):
        return True
    # Doesn't fall in any of the above cases:
    return False


def ip(xy1,xy2):
    ax,ay,bx,by = xy1; cx,cy,dx,dy = xy2
    dn = ((by-ay)*(dx-cx)-(bx-ax)*(dy-cy))*1.0
    x = ((cy*dx-cx*dy)*(bx-ax)-(ay*bx-ax*by)*(dx-cx))/dn
    y = ((cy*dx-cx*dy)*(by-ay)-(ay*bx-ax*by)*(dy-cy))/dn
    return x,y
 
def stoning_fortune(coord1, coord2, coord3):
    p1, q1 = coord1[:2], coord1[2:]
    p2, q2 = coord2[:2], coord2[2:]
    p3, q3 = coord3[:2], coord3[2:]
    if not do_intersect(p1, q1, p2, q2) or not do_intersect(p1, q1, p3, q3) or \
       not do_intersect(p3, q3, p2, q2) :
        return "kyo"
    x1, y1 = ip(coord1, coord2)
    x2, y2 = ip(coord2, coord3)
    x3, y3 = ip(coord3, coord1)
    area = abs(.5 * (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
    if area >= 1900000:
        return "dai-kichi"
    elif area >= 1000000:
        return "chu-kichi"
    elif area >= 100000:
        return "kichi"
    elif area > 0:
        return "syo-kichi"
    else:
        return "kyo"
    
    
while True:
    coord1 = [int(_) for _ in input().split()]
    if coord1 == [0, 0, 0, 0]:
        break
    coord2 = [int(_) for _ in input().split()]
    coord3 = [int(_) for _ in input().split()]
    print(stoning_fortune(coord1, coord2, coord3))

Submission status: Accepted

Solution code:
def cross3(O, A, B):
    ox, oy = O; ax, ay = A; bx, by = B
    return (ax - ox) * (by - oy) - (bx - ox) * (ay - oy)
def outer(x0, y0, x1, y1):
    return x0*y1 - x1*y0
def is_intersection(P0, P1, Q0, Q1):
    C0 = cross3(P0, P1, Q0)
    C1 = cross3(P0, P1, Q1)
    D0 = cross3(Q0, Q1, P0)
    D1 = cross3(Q0, Q1, P1)
    if C0 == C1 == 0:
        return 0
    return C0 * C1 <= 0 and D0 * D1 <= 0
def cross_point(P0, Q0, P1, Q1):
    x0, y0 = P0; x1, y1 = Q0
    x2, y2 = P1; x3, y3 = Q1
    dx0 = x1 - x0
    dy0 = y1 - y0
    dx1 = x3 - x2
    dy1 = y3 - y2

    s = (y0-y2)*dx1 - (x0-x2)*dy1
    sm = dx0*dy1 - dy0*dx1
    if s < 0:
        s = -s
        sm = -sm
    if s == 0:
        x = x0
        y = y0
    else:
        x = x0 + s*dx0/sm
        y = y0 + s*dy0/sm
    return x, y
while 1:
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == y1 == x2 == y2 == 0:
        break
    P1 = (x1, y1); Q1 = (x2, y2)
    x3, y3, x4, y4 = map(int, input().split())
    P2 = (x3, y3); Q2 = (x4, y4)
    x5, y5, x6, y6 = map(int, input().split())
    P3 = (x5, y5); Q3 = (x6, y6)
    if (not is_intersection(P1, Q1, P2, Q2)
            or not is_intersection(P2, Q2, P3, Q3)
            or not is_intersection(P3, Q3, P1, Q1)):
        print("kyo")
        continue
    p1, q1 = cross_point(P1, Q1, P2, Q2)
    p2, q2 = cross_point(P2, Q2, P3, Q3)
    p3, q3 = cross_point(P3, Q3, P1, Q1)
    S = abs(outer(p2-p1, q2-q1, p3-p1, q3-q1)) / 2.
    if S < 1e-9:
        print("kyo")
    elif S < 100000:
        print("syo-kichi")
    elif S < 1000000:
        print("kichi")
    elif S < 1900000:
        print("chu-kichi")
    else:
        print("dai-kichi")