Problem:


かくれんぼう

たろう君はかくれんぼうが苦手です。隠れるとすぐ見つかっちゃうし、隠れている子をなかなか見つけることができません。見かねたお父さんは、超高性能位置探索システムを作ってくれました。これを使うと自分の位置を含めて、友達の位置を正確に知ることができます。鬼になったら、隠れている子を探すことが簡単にできるようになりました。

たろう君はさらにこのシステムを進化させ、鬼から自分が見えるか否かを判定する機能を付加することを思いつきました。これができれば、「もういいかい」と言われても、見える位置にいれば「まあだだよ」だし、見えない位置にいれば「もういいよ」ですね。いつも遊んでいる公園には大小さまざまな円筒形の壁があります。この壁は外からは中は見えないし、中から外も見えません。鬼と一緒に中に入ると別の壁がなければ見えちゃいます。

たろう君はアイデアはいいのですが、ソフトを作るのが苦手です。そこで親友のあなたはたろう君に代わって、「鬼から見えないこと確認システム」のソフトウェアを作ることになりました。公園の壁は固定されていますが、たろう君と鬼のいろいろな位置情報に対して見えるか否かを判定する必要があります。

公園にある壁の情報(中心の座標 (wx, wy) と 半径 r) とたろう君と鬼の位置情報(たろう君の位置の座標 (tx, ty) と鬼の位置の座標 (sx, sy) ) を入力とし、その位置で鬼からたろう君が見えるか否かを判定するプログラムを作成してください。

なお、鬼からたろう君が見える場合には Danger、見えない場合には Safe と出力してください。鬼とたろう君の位置を結んだ線分上に壁がある場合には見えないものとし、鬼もたろう君も壁の上にはいないものとします。

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

n
wx1 wy1 r1
wx2 wy2 r2
:
wxn wyn rn
m
tx1 ty1 sx1 sy1
tx2 ty2 sx2 sy2
:
txm tym sxm sym

1 行目に円筒形の壁の数 n (0 ≤ n ≤ 100)、続く n 行に壁 i の中心の座標を表す整数 wxi, wyi (0 ≤ wxi, wyi ≤ 255) と半径を表す整数 ri (1 ≤ ri ≤ 255) が与えられます。

続く行にたろう君と鬼の位置情報の個数 m (m ≤ 100)、続く m 行に位置情報 i のたろう君の位置の座標を表す整数 txi, tyi (0 ≤ txi, tyi  ≤ 255) と鬼の位置の座標を表す整数 sxi, syi (0 ≤ sxi, syi ≤ 255)  が与えられます。

また、円筒形の壁の一部だけが公園にあるということはなく、全ての壁は円筒として、公園の内部に入っています。

n が 0 のとき入力の終わりを示します。データセットの数は 20 を超えません。

Output

各データセットについて、位置情報 i の判定結果 Danger または Safe を i 行目に出力してください。

Sample Input

3
6 6 3
19 7 4
21 8 1
6
5 4 2 11
12 4 2 11
11 9 2 11
14 3 20 5
17 9 20 5
20 10 20 5
0

Output for the Sample Input

Safe
Safe
Danger
Safe
Danger
Safe



Sample input:
3
6 6 3
19 7 4
21 8 1
6
5 4 2 11
12 4 2 11
11 9 2 11
14 3 20 5
17 9 20 5
20 10 20 5
0


Sample output:
Safe
Safe
Danger
Safe
Danger
Safe

Submission status: Accepted

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

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



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 isinstance(s, Point):
            return sqrt((self.x - s.x)**2 + (self.y - s.y)**2)
        if isinstance(s, Segment):
            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 Circle(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, Circle):
            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


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        circles = []
        for _ in range(n):
            x, y, r = map(int, input().split())
            p = Point(x, y)
            circles.append(Circle(p, r))
        m = int(input())
        for _ in range(m):
            tx, ty, sx, sy = map(int, input().split())
            taro = Point(tx, ty)
            oni = Point(sx, sy)
            s = Segment(taro, oni)
            is_safe = False
            for c in circles:
                x, y, r = c.c.x, c.c.y, c.r
                if taro.distance(Point(x, y)) < r and oni.distance(Point(x, y)) < r:
                    continue
                if Point(x, y).distance(s) <= r:
                    is_safe = True
                    break
            if is_safe:
                print('Safe')
            else:
                print('Danger')


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

Submission status: Accepted

Solution code:
class Wall():

    def __init__(self, x, y, r):
        self.x = x
        self.y = y
        self.r = r

    def sign(self, x, y):
        if (x-self.x)*(x-self.x) + (y-self.y)*(y-self.y) - self.r*self.r > 0:
            return 1
        else:
            return -1

def isVisible(x1, y1, x2, y2, wall):

    if wall.sign(x1, y1) == 1 and wall.sign(x2, y2) == 1:

        x0 = wall.x
        y0 = wall.y
        r0 = wall.r

        la = y2-y1
        lb = -(x2-x1)
        lc = -x1*(y2-y1) + y1*(x2-x1)

        ma = x2-x1
        mb = y2-y1
        mc = -(x2-x1)*x0 - (y2-y1)*y0

        if (la*x0+lb*y0+lc)*(la*x0+lb*y0+lc) <= r0*r0*(la*la+lb*lb):
            if (ma*x1+mb*y1+mc)*(ma*x2+mb*y2+mc) < 0:
                return False
            else:
                return True
        else:
            return True
    elif wall.sign(x1, y1) == -1 and wall.sign(x2, y2) == -1:
        return True
    else:
        return False


while True:
    n = int(input())
    if n == 0:
        break

    walls = []
    for l in range(n):
        x,y,r = [int(i) for i in input().split()]
        walls.append(Wall(x,y,r))

    m = int(input())
    for l in range(m):
        tx, ty, sx, sy = [int(i) for i in input().split()]
        ans = "Danger"
        for k in range(len(walls)):
            if isVisible(tx, ty, sx, sy, walls[k]) == False:
                #print("Wall", k+1, ": Safe")
                ans = "Safe"
                break
        print(ans)

Submission status: Accepted

Solution code:
from __future__ import division
from collections import namedtuple
import math
Vector=namedtuple('Vector','x y')

def size(H):
    return math.sqrt(pow(H.x,2)+pow(H.y,2))

def inner(A,B):
    return A.x*B.x+A.y*B.y

def collision(tx,ty,sx,sy,px,py,r):
    #if collision: return True
    #else: return False
    S=Vector(x=tx-sx,y=ty-sy)
    A=Vector(x=px-sx,y=py-sy)
    B=Vector(x=px-tx,y=py-ty)
    d=abs(S.x*A.y-A.x*S.y)/size(S)
#    print d,r,inner(A,S)*inner(B,S),size(A),size(B),px,py,r
    if d>r:
        return False
    elif r>size(A) and r>size(B):
        return False
    elif inner(A,S)*inner(B,S)<=0:
        return True
    elif r>size(A) or r>size(B):
        return True
    else:
        return False

while True:
    n=input()
    if n==0:break
    wall=[map(int,raw_input().split()) for i in range(n)]
    m=input()
    for i in range(m):
        tx,ty,sx,sy=map(int,raw_input().split())
        for wx,wy,r in wall:
            if collision(tx,ty,sx,sy,wx,wy,r):
                print 'Safe'
                break
        else:
            print 'Danger'

Submission status: Accepted

Solution code:
def inWall(x,y,x1,y1,r):
	return True if ((x-x1)**2+(y-y1)**2)**0.5 <= r + 1e-9 else False

def isHide(x,y,r,a,b,c):
	D = abs(a*x+b*y+c)/(a**2+b**2)**0.5
	return True if D <= r + 1e-9 else False

def isBetween(x,y,tx,ty,sx,sy):
	a,b,c = (x-tx)**2+(y-ty)**2,(x-sx)**2+(y-sy)**2,(sx-tx)**2+(sy-ty)**2
	if c > b and c > a: return True
	a,b,c = sorted([a,b,c])
	return True if c-a-b <= 0 else False

while 1:
	n = input()
	if n == 0: break
	wall = [map(int,raw_input().split()) for i in range(n)]
	for i in range(input()):
		tx,ty,sx,sy = map(int,raw_input().split())
		a,b,c = -(ty-sy),tx-sx,sx*ty-sy*tx
		for x,y,r in wall:
			t_in,s_in = inWall(x,y,tx,ty,r),inWall(x,y,sx,sy,r)
			if t_in != s_in:
				print "Safe"
				break
			if not t_in and isBetween(x,y,tx,ty,sx,sy) and isHide(x,y,r,a,b,c):
				print "Safe"
				break
		else:
			print "Danger"

Submission status: Accepted

Solution code:
def dist(x,y,x1,y1):
	return (x-x1)**2+(y-y1)**2
	
def inWall(x,y,x1,y1,r):
 	return True if dist(x,y,x1,y1) <= (r + 1e-9)**2 else False

def isHide(x,y,r,a,b,c):
	D = abs(a*x+b*y+c)/(a**2+b**2)**0.5
	return True if D <= r + 1e-9 else False

def isBetween(x,y,tx,ty,sx,sy):
	a,b,c = dist(x,y,tx,ty),dist(x,y,sx,sy),dist(tx,ty,sx,sy)
	if c > b and c > a: return True
	a,b,c = sorted([a,b,c])
	return True if c-a-b <= 0 else False

while 1:
	n = input()
	if n == 0: break
	wall = [map(int,raw_input().split()) for i in range(n)]
	for i in range(input()):
		tx,ty,sx,sy = map(int,raw_input().split())
		a,b,c = -(ty-sy),tx-sx,sx*ty-sy*tx
		for x,y,r in wall:
			t_in,s_in = inWall(x,y,tx,ty,r),inWall(x,y,sx,sy,r)
			if t_in != s_in or (not t_in and isBetween(x,y,tx,ty,sx,sy) and isHide(x,y,r,a,b,c)):
				print "Safe"
				break
		else:
			print "Danger"

Submission status: Accepted

Solution code:
def inWall(x,y,x1,y1,r):
	return True if ((x-x1)**2+(y-y1)**2)**0.5 <= r + 1e-9 else False

def isHide(x,y,r,a,b,c):
	D = abs(a*x+b*y+c)/(a**2+b**2)**0.5
	return True if D <= r + 1e-9 else False

def isBetween(x,y,tx,ty,sx,sy):
	a,b,c = (x-tx)**2+(y-ty)**2,(x-sx)**2+(y-sy)**2,(sx-tx)**2+(sy-ty)**2
	if c > b and c > a: return True
	a,b,c = sorted([a,b,c])
	return True if c-a-b <= 0 else False

while 1:
	n = input()
	if n == 0: break
	wall = [map(int,raw_input().split()) for i in range(n)]
	for i in range(input()):
		tx,ty,sx,sy = map(int,raw_input().split())
		a,b,c = -(ty-sy),tx-sx,sx*ty-sy*tx
		for x,y,r in wall:
			t_in,s_in = inWall(x,y,tx,ty,r),inWall(x,y,sx,sy,r)
			if t_in != s_in or (not t_in and isBetween(x,y,tx,ty,sx,sy) and isHide(x,y,r,a,b,c)):
				print "Safe"
				break
		else:
			print "Danger"

Submission status: Accepted

Solution code:
def inWall(x,y,x1,y1,r):
	return True if ((x-x1)**2+(y-y1)**2)**0.5 <= r + 1e-9 else False

def isHide(x,y,r,a,b,c):
	D = abs(a*x+b*y+c)/(a**2+b**2)**0.5
	return True if D <= r + 1e-9 else False

def isBetween(x,y,tx,ty,sx,sy):
	a,b,c = (x-tx)**2+(y-ty)**2,(x-sx)**2+(y-sy)**2,(sx-tx)**2+(sy-ty)**2
	if c > b and c > a: return True
	a,b,c = sorted([a,b,c])
	return True if c-a-b <= 0 else False

while 1:
	n = input()
	if n == 0: break
	wall = [map(int,raw_input().split()) for i in range(n)]
	for i in range(input()):
		tx,ty,sx,sy = map(int,raw_input().split())
		a,b,c = -(ty-sy),tx-sx,sx*ty-sy*tx
		for x,y,r in wall:
			t_in,s_in = inWall(x,y,tx,ty,r),inWall(x,y,sx,sy,r)
			if t_in != s_in or (not t_in and isHide(x,y,r,a,b,c) and isBetween(x,y,tx,ty,sx,sy)):
				print "Safe"
				break
		else:
			print "Danger"

Submission status: Accepted

Solution code:
from math import sqrt
def intersection(cx, cy, r, P1, P2):
    x1, y1 = P1; x2, y2 = P2

    xd = x2 - x1; yd = y2 - y1
    X = x1 - cx; Y = y1 - cy
    a = xd**2 + yd**2
    b = xd * X + yd * Y
    c = X**2 + Y**2 - r**2

    f0 = c; f1 = a+2*b+c
    if (f0 >= 0 and f1 <= 0) or (f0 <= 0 and f1 >= 0):
        return True
    return -a <= b <= 0 and b**2 - a*c >= 0 and (f0 >= 0 or f1 >= 0)

def solve():
    N = int(input())
    if N == 0:
        return False
    C = []
    for i in range(N):
        x, y, r = map(int, input().split())
        C.append((x, y, r))
    M = int(input())
    for i in range(M):
        tx, ty, sx, sy = map(int, input().split())
        for j in range(N):
            cx, cy, r = C[j]
            if intersection(cx, cy, r, (tx, ty), (sx, sy)):
                print("Safe")
                break
        else:
            print("Danger")
    return True
while solve():
    ...

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
      if (a>b or abs(a-b)<1e-6) and rst>(rsw**2-r**2)**.5: c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
      if (a>=b or abs(a-b)<1e-6) and rst>=(rsw**2-r**2)**.5: c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    c=0
    if rst==0: c=1
    elif F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
#      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
#      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      tmp=(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      if abs(abs(tmp)-1)<1e-6: tmp=1
      b=M.acos(tmp)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      tmp=(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      if abs(abs(tmp)-1)<1e-6: tmp=1
      b=M.acos(tmp/2)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      tmp=(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      if abs(abs(tmp)-1)<1e-6: tmp=1
      b=0#M.acos(tmp/2)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      tmp=0#(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      if abs(abs(tmp)-1)<1e-6: tmp=1
      b=0#M.acos(tmp/2)
      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1 # 両方壁の中
    elif F==[1,0] or F==[0,1]: c=0 # 片方が壁の中
    elif F==[0,0]: #両方壁の外
      a=M.pi/2-M.acos(r/rsw)
      #tmp=0#(sw[0]*st[0]+sw[1]*st[1])/rsw/rst
      #if abs(abs(tmp)-1)<1e-6: tmp=1
      b=0#M.acos(tmp/2)
      #if C(a,b) and C(rst**2,rsw**2-r**2): c=0
      #else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math as M
def R(A): return (A[0]**2+A[1]**2)**.5
def I(i): return [map(int,raw_input().split()) for _ in [0]*i]
def C(a,b): return a>b or abs(a-b)<1e-6
def f(e1):
  tx,ty,sx,sy=e1
  x=[]
  for e2 in WP:
    wx,wy,r=e2
    wt=[tx-wx,ty-wy]; rwt=R(wt)
    sw=[wx-sx,wy-sy]; rsw=R(sw)
    st=[tx-sx,ty-sy]; rst=R(st)
    F=[rwt<r,rsw<r]
    if rst==0: c=1
    elif F==[1,1]: c=1
    elif F==[1,0] or F==[0,1]: c=0
    elif F==[0,0]:
      c=0
      a=M.pi/2-M.acos(r/rsw)
      b=M.acos((sw[0]*st[0]+sw[1]*st[1])/rsw/rst)
#      if C(a,b) and C(rst**2,rsw**2-r**2): c=0
#      else: c=1
    x.append(c)
  return all(x)

while 1:
  n=input()
  if n==0: break
  WP=I(n)
  P=I(input())
  for e in P: print ["Safe","Danger"][f(e)]

Submission status: Runtime Error

Solution code:
import math

def f():
    x = 0; y = 1; r = 2
    for w in L_w:
        A = (tx-w[x])**2 + (ty-w[y])**2 - w[r]**2
        B = (sx-w[x])**2 + (sy-w[y])**2 - w[r]**2
        if 0 < A and 0 < B and (tx-w[w])*(sx-w[x]) < 0:
            P = abs((sy-ty)*w[x] - (sx-tx)*w[y] - (sy-ty)*tx + ty)
            Q = math.sqrt((sy-ty)**2 + (sx-tx)**2)
            print (float(P)/Q)
            if (float(P)/Q) <= w[r]:
                print 'Safe'
                break
        elif A*B < 0:
            print 'Safe'
            break
    else:
        print 'Danger'
   
while True:
    N = input()
    if N == 0: break
    L_w = [map(int, raw_input().split()) for i in range(N)]
    for i in range(input()):
        tx, ty, sx, sy = map(int, raw_input().split())
        f()