Problem:


三角形と円

平面上にある三角形と円の位置関係を判定するプログラムを作成してください。対象となる図形はいずれも境界を含むものとします。
三角形は 3 頂点の位置が与えられ、円は中心の位置と半径が与えられます。位置は直交座標系による２つの整数の組によって与えられます。半径も整数で与えられます。

Input

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

x1 y1
x2 y2
x3 y3
xc yc
r

１行目から３行目に、三角形の第 i の頂点座標 xi, yi が与えられます。４行目に円の中心の座標 xc, yc、５行目に円の半径 r が与えられます。与えられる入力はすべて、1 以上 10,000 以下の整数とします。

データセットの数は 100 を超えません。

Output

入力データセットごとに以下の形式で判定結果を１行に出力します。

円が三角形に含まれる場合 a

三角形が円に含まれる場合 b

それ以外の場合で、共通部分がある場合には c

共通部分がない場合には d

Sample Input

1 1
3 1
3 3
3 2
3
3 12
9 3
11 12
8 7
5
15 3
17 7
22 5
7 6
4
6 11
8 2
16 9
10 8
2
0 0

Output for the Sample Input

b
c
d
a



Sample input:
1 1
3 1
3 3
3 2
3
3 12
9 3
11 12
8 7
5
15 3
17 7
22 5
7 6
4
6 11
8 2
16 9
10 8
2
0 0


Sample output:
b
c
d
a

Submission status: Wrong Answer

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
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,p0,p1,p2): return (side(p0,p1,x)==side(p1,p2,x)==side(p2,p0,x))
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def CinT(P4,r,P1,P2,P3):
  f1 = isIn(P4,P1,P2,P3)
  f = [H(P4,P1,P2)>=r, H(P4,P2,P3)>=r, H(P4,P3,P1)>=r]
  if f1:
    if all(f): return 1
    elif any(f): return 3
  return 0

def TinC(P4,r,P1,P2,P3):
  f = [D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]
  if all(f): return 2
  elif any(f): return 3
  return 0
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  f = CinT(P4,r,P1,P2,P3)
  if not f: f = TinC(P4,r,P1,P2,P3)
  print 'dabc'[f]

Submission status: Wrong Answer

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
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,p0,p1,p2): return (side(p0,p1,x)==side(p1,p2,x)==side(p2,p0,x))
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def check(P4,r,P1,P2,P3):
  f1 = isIn(P4,P1,P2,P3)
  f = [H(P4,P1,P2)>=r, H(P4,P2,P3)>=r, H(P4,P3,P1)>=r]
  if f1:
    if all(f): return 1
    elif sum(f)>0: return 3
  f = [D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]
  if all(f): return 2
  elif sum(f)>0: return 3
  return 0
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]

Submission status: Wrong Answer

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
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,p0,p1,p2): return (side(p0,p1,x)==side(p1,p2,x)==side(p2,p0,x))
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def check(P4,r,P1,P2,P3):
  if all([D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]): return 2
  h1 = H(P4,P1,P2)
  h2 = H(P4,P2,P3)
  h3 = H(P4,P3,P1)
  if isIn(P4,P1,P2,P3):
    if all([h1>=r, h2>=r, h3>=r]): return 1
  else:
    if all([h1>r, h2>r, h3>r]): return 0
  return 3
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]

Submission status: Wrong Answer

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
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,p0,p1,p2): return (side(p0,p1,x)==side(p1,p2,x)==side(p2,p0,x))
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def check(P4,r,P1,P2,P3):
  if all([D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]): return 2
  h1 = H(P4,P1,P2)
  h2 = H(P4,P2,P3)
  h3 = H(P4,P3,P1)
  if isIn(P4,P1,P2,P3):
    if all([h1>=r, h2>=r, h3>=r]): return 1
  else:
    if all([h1>r, h2>r, h3>r]): return 0
  return 3
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]

Submission status: Wrong Answer

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
def side(a, b, c):
  f = (c[1]-a[1])*(b[0]-a[0])-(b[1]-a[1])*(c[0]-a[0])
  if f>0: return 1
  elif f<0: return -1
  else: return 0
def isIn(x,p0,p1,p2):
  f = [side(p0,p1,x), side(p1,p2,x), side(p2,p0,x)]
  return min(f)>=0 or max(f)<=0
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def check(P4,r,P1,P2,P3):
  if all([D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]): return 2
  h1 = H(P4,P1,P2)
  h2 = H(P4,P2,P3)
  h3 = H(P4,P3,P1)
  if isIn(P4,P1,P2,P3):
    if all([h1>=r, h2>=r, h3>=r]): return 1
  else:
    if all([h1>r, h2>r, h3>r]): return 0
  return 3
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]

Submission status: Wrong Answer

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


class Points(object):
    pass


def sub_vector(a, b):
    ret = Points()
    ret.x = a.x - b.x
    ret.y = a.y - b.y
    return ret


def hittest_point_polygon(a, b, c, p):
    ab = sub_vector(b, a)
    bp = sub_vector(p, b)
    bc = sub_vector(c, b)
    cp = sub_vector(p, c)
    ca = sub_vector(a, c)
    ap = sub_vector(p, a)

    #外積    Z成分だけ計算すればよいです
    c1 = ab.x * bp.y - ab.y * bp.x
    c2 = bc.x * cp.y - bc.y * cp.x
    c3 = ca.x * ap.y - ca.y * ap.x

    if (c1 > 0 and c2 > 0 and c3 > 0) or (c1 < 0 and c2 < 0 and c3 < 0):
        #三角形の内側に点がある
        return True
    #三角形の外側に点がある
    return False


def get_dist(a, b):
    return math.sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2))

f = lambda: map(int, raw_input().split())
while True:
    a, b, c, p = [Points() for i in range(4)]
    a.x, a.y = f()
    if a.x == a.y == 0: break
    b.x, b.y = f()
    c.x, c.y = f()
    p.x, p.y = f()
    r = input()
    if hittest_point_polygon(a, b, c, p) and get_dist(p, a) > r and get_dist(p, b) > r and get_dist(p, c) > r:
        print "a"
    elif get_dist(p, a) < r and get_dist(p, b) < r and get_dist(p, c) < r:
        print "b"
    elif get_dist(p, a) < r or get_dist(p, b) < r or get_dist(p, c) < r:
        print "c"
    else:
        print "d"

Submission status: Wrong Answer

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


class Points(object):
    pass


def sub_vector(a, b):
    ret = Points()
    ret.x = a.x - b.x
    ret.y = a.y - b.y
    return ret


def hittest_point_polygon(a, b, c, p):
    ab = sub_vector(b, a)
    bp = sub_vector(p, b)
    bc = sub_vector(c, b)
    cp = sub_vector(p, c)
    ca = sub_vector(a, c)
    ap = sub_vector(p, a)

    #外積    Z成分だけ計算すればよいです
    c1 = ab.x * bp.y - ab.y * bp.x
    c2 = bc.x * cp.y - bc.y * cp.x
    c3 = ca.x * ap.y - ca.y * ap.x

    if (c1 > 0 and c2 > 0 and c3 > 0) or (c1 < 0 and c2 < 0 and c3 < 0):
        #三角形の内側に点がある
        return True
    #三角形の外側に点がある
    return False


def get_dist(a, b):
    return math.sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2))

f = lambda: map(int, raw_input().split())
while True:
    a, b, c, p = [Points() for i in range(4)]
    a.x, a.y = f()
    if a.x == a.y == 0: break
    b.x, b.y = f()
    c.x, c.y = f()
    p.x, p.y = f()
    r = input()
    if hittest_point_polygon(a, b, c, p) and get_dist(p, a) >= r and get_dist(p, b) >= r and get_dist(p, c) >= r:
        print "a"
    elif get_dist(p, a) <= r and get_dist(p, b) <= r and get_dist(p, c) <= r:
        print "b"
    elif get_dist(p, a) <= r or get_dist(p, b) <= r or get_dist(p, c) <= r:
        print "c"
    else:
        print "d"

Submission status: Wrong Answer

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


class Points(object):
    pass


def sub_vector(a, b):
    ret = Points()
    ret.x = a.x - b.x
    ret.y = a.y - b.y
    return ret


def hittest_point_polygon(a, b, c, p):
    ab = sub_vector(b, a)
    bp = sub_vector(p, b)
    bc = sub_vector(c, b)
    cp = sub_vector(p, c)
    ca = sub_vector(a, c)
    ap = sub_vector(p, a)

    #外積    Z成分だけ計算すればよいです
    c1 = ab.x * bp.y - ab.y * bp.x
    c2 = bc.x * cp.y - bc.y * cp.x
    c3 = ca.x * ap.y - ca.y * ap.x

    if (c1 > 0 and c2 > 0 and c3 > 0) or (c1 < 0 and c2 < 0 and c3 < 0):
        #三角形の内側に点がある
        return True
    #三角形の外側に点がある
    return False


def get_dist(a, b):
    return math.sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2))


def naisetsu_r(p1, p2, p3):
    a = get_dist(p1, p2)
    b = get_dist(p1, p3)
    c = get_dist(p2, p3)
    s = (a + b + c) / 2
    S = math.sqrt(s * (s-a) * (s-b) * (s-c))
    return S / s

f = lambda: map(int, raw_input().split())
while True:
    a, b, c, p = [Points() for i in range(4)]
    a.x, a.y = f()
    if a.x == a.y == 0: break
    b.x, b.y = f()
    c.x, c.y = f()
    p.x, p.y = f()
    r = input()
    if hittest_point_polygon(a, b, c, p) and naisetsu_r(a, b, c) >= r:
        print "a"
    elif get_dist(p, a) <= r and get_dist(p, b) <= r and get_dist(p, c) <= r:
        print "b"
    elif get_dist(p, a) <= r or get_dist(p, b) <= r or get_dist(p, c) <= r:
        print "c"
    else:
        print "d"

Submission status: Accepted

Solution code:
def In():
  return map(int, raw_input().split())

def D(a, b): # diatance between a and b
  return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** .5

def f(P, O): # make a vector from O to P
  return P[0] - O[0], P[1] - O[1]

def dot(a, b): #inner product of vectors a and b
  return a[0] * b[0] + a[1] * b[1]

def cross(a, b): #cross product of vectors a and b
  return a[0] * b[1] - a[1] * b[0]

def ab2c(a, b, c): # distance from point c to segment a-b
  if dot(f(c, a), f(b, a)) < 0:
    return D(a, c)
  if dot(f(c, b), f(a, b)) < 0:
    return D(b, c)
  return abs(cross(f(b, a), f(c, a))) / D(b, a)

def isIn(P, O, P1, P2): # check if point P is in triangle O-P1-P2
  a11, a21 = f(P1, O)
  a12, a22 = f(P2, O)
  x0, y0 = f(P, O)
  det = 1.0 * a11 * a22 - a12 * a21
  x = (a22 * x0 - a12 * y0) / det
  y = (-a21 * x0 + a11 * y0) / det
  return 0 <= x <= 1 and 0 <= y <= 1 and 0 <= x + y <= 1
def check(P4, r, P1, P2, P3):
  if max([D(P4, P1), D(P4, P2), D(P4, P3)]) <= r:
    return 2
  h1 = ab2c(P1, P2, P4)
  h2 = ab2c(P2, P3, P4)
  h3 = ab2c(P3, P1, P4)
  if isIn(P4, P1, P2, P3):
    if min([h1, h2, h3]) >= r:
      return 1
  elif min([h1, h2, h3]) > r:
    return 0
  return 3

while 1:
  P1 = In()
  if P1[0] == P1[1] == 0:
    break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4, r, P1, P2, P3)]

Submission status: Accepted

Solution code:
def In(): return map(int, raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
def f(P,O): return P[0]-O[0], P[1]-O[1]
def dot(a,b): return a[0]*b[0]+a[1]*b[1]
def cross(a,b): return a[0]*b[1]-a[1]*b[0]

def ab2c(a,b,c):
  if dot(f(c,a),f(b,a))<0: return D(a,c)
  if dot(f(c,b),f(a,b))<0: return D(b,c)
  return abs(cross(f(b,a),f(c,a)))/D(b,a)

def isIn(P,O,P1,P2):
  a11,a21 = f(P1,O)
  a12,a22 = f(P2,O)
  x0,y0 = f(P,O)
  det = 1.0*a11*a22-a12*a21
  x = (a22*x0-a12*y0)/det
  y = (-a21*x0+a11*y0)/det
  return 0<=x<=1 and 0<=y<=1 and 0<=x+y<=1

def check(P4,r,P1,P2,P3):
  if max([D(P4,P1),D(P4,P2),D(P4,P3)])<=r: return 2
  h1 = ab2c(P1,P2,P4)
  h2 = ab2c(P2,P3,P4)
  h3 = ab2c(P3,P1,P4)
  if isIn(P4,P1,P2,P3):
    if min([h1,h2,h3])>=r: return 1
  elif min([h1,h2,h3])>r: return 0
  return 3

while 1:
  P1 = In()
  if P1[0]== P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]

Submission status: Accepted

Solution code:
def contain(x, y, r):
    return x**2 + y**2 <= r**2
def outer_p(x0, y0, x1, y1):
    return (x0*y1 - y0*x1)
def line_segment_circle(x0, y0, x1, y1, r, border=True):
    A = x0**2 + y0**2
    B = x0*x1 + y0*y1
    C = x1**2 + y1**2 - r**2
    D = B**2 - A*C
    if border:
        if D < 0:
            return 0
        if B <= 0 and B**2 > D:
            return 0
        if B - A >= 0 and (B - A)**2 > D:
            return 0
    else:
        if D <= 0:
            return 0
        if B <= 0 and B**2 >= D:
            return 0
        if B - A >= 0 and (B - A)**2 >= D:
            return 0
    return 1

while 1:
    x1, y1 = map(int, input().split())
    if x1 == y1 == 0:
        break
    x2, y2 = map(int, input().split())
    x3, y3 = map(int, input().split())

    cx, cy = map(int, input().split())
    r = int(input())

    C1 = contain(x1-cx, y1-cy, r)
    C2 = contain(x2-cx, y2-cy, r)
    C3 = contain(x3-cx, y3-cy, r)
    if C1 and C2 and C3:
        print("b")
        continue
    if C1 or C2 or C3:
        print("c")
        continue
    p1 = outer_p(x2-x1, y2-y1, cx-x1, cy-y1)
    p2 = outer_p(x3-x2, y3-y2, cx-x2, cy-y2)
    p3 = outer_p(x1-x3, y1-y3, cx-x3, cy-y3)
    if 1 == (p1 < 0) == (p2 < 0) == (p3 < 0) or 1 == (p1 > 0) == (p2 > 0) == (p3 > 0):
        p1 = line_segment_circle(x2-x1, y2-y1, cx-x1, cy-y1, r, False)
        p2 = line_segment_circle(x3-x2, y3-y2, cx-x2, cy-y2, r, False)
        p3 = line_segment_circle(x1-x3, y1-y3, cx-x3, cy-y3, r, False)
        if p1 or p2 or p3:
            print("c")
        else:
            print("a")
        continue
    p1 = line_segment_circle(x2-x1, y2-y1, cx-x1, cy-y1, r, True)
    p2 = line_segment_circle(x3-x2, y3-y2, cx-x2, cy-y2, r, True)
    p3 = line_segment_circle(x1-x3, y1-y3, cx-x3, cy-y3, r, True)
    if p1 or p2 or p3:
        print("c")
        continue
    print("d")

Submission status: Runtime Error

Solution code:
def In(): return map(int,raw_input().split())
def D(a,b): return ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
def side(a, b, c):
  f = (c[1]-a[1])*(b[0]-a[0])-(b[1]-a[1])*(c[0]-a[0])
  if f>0: return 1
  elif f<0: return -1
  else return 0
def isIn(x,p0,p1,p2):
  f1 = side(p0,p1,x)
  f2 = side(p1,p2,x)
  f3 = side(p2,p0,x)
  return (f1>=0 and f2>=0 and f3>=0) or (f1<=0 and f2<=0 and f3<=0)
def S(a,b,c): return abs(a[0]*(b[1]-c[1])+b[0]*(c[1]-a[1])+c[0]*(a[1]-b[1]))/2.0
def H(P1,P2,P3): return 2*S(P1,P2,P3)/D(P2,P3)
def check(P4,r,P1,P2,P3):
  if all([D(P4,P1)<=r, D(P4,P2)<=r, D(P4,P3)<=r]): return 2
  h1 = H(P4,P1,P2)
  h2 = H(P4,P2,P3)
  h3 = H(P4,P3,P1)
  if isIn(P4,P1,P2,P3):
    if all([h1>=r, h2>=r, h3>=r]): return 1
  else:
    if all([h1>r, h2>r, h3>r]): return 0
  return 3
  
while 1:
  P1 = In()
  if P1[0]==P1[1]==0: break
  P2 = In()
  P3 = In()
  P4 = In()
  r = int(raw_input())
  print 'dabc'[check(P4,r,P1,P2,P3)]