Watson gives a circle and a triangle in a 2-dimensional plane to Sherlock. Sherlock has to tell if they intersect/touch each other. 

The circle is centered at $(x_c,y_c)$ and has radius $\mbox{R}$.   

Input Format 

The first line contains $\mathbf{T}$, the number of test cases. 

Each test case consists of $x_c$, $\boldsymbol{y}_{c}$ and $\mbox{R}$ in one line. 

The next three lines each contains $x_i,y_i$ denoting the vertices of the triangle.   

Output Format 

For each test case, print YES if the triangle touches or intersects the circle; otherwise, print NO.   

Constraints 

$1\leq T\leq30000$ 

$1\leq R\leq2000$ 

$-2000\leq x_c,y_c\leq2000$ 

$-5000\leq x_i,y_i\leq5000$ 

Note: There will be no degenerate triangles (i.e. triangles with area 0)  

Sample Input  

2
0 0 10
10 0
15 0
15 5
0 0 10
0 0
5 0
5 5

Sample Output    

YES
NO

Explanation 

In the first case, the triangle is touching the circle. In the second case, it neither touches nor intersects the circle.

Difficulty: HARD
Tags: Geometry

Starter code:

Solutions:
from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


T = int(input())
get = lambda : map(int, input().split())
for t in range(T):
	(xc, yc, R) = get()
	(x1, y1) = get()
	(x2, y2) = get()
	(x3, y3) = get()

	def in_circle(x, y):
		return (x - xc) ** 2 + (y - yc) ** 2 < R * R

	def on_circle(x, y):
		return (x - xc) ** 2 + (y - yc) ** 2 == R * R

	def check(x1, y1, x2, y2):
		in1 = in_circle(x1, y1)
		in2 = in_circle(x2, y2)
		if in1 != in2:
			return True
		if in1:
			return False
		if ((x2 - x1) * (y1 - yc) - (x1 - xc) * (y2 - y1)) ** 2 > R * R * ((x2 - x1) ** 2 + (y2 - y1) ** 2):
			return False
		return (x2 - x1) * (x1 - xc) + (y2 - y1) * (y1 - yc) < 0 and (x1 - x2) * (x2 - xc) + (y1 - y2) * (y2 - yc) < 0
	if on_circle(x1, y1) or on_circle(x2, y2) or on_circle(x3, y3) or check(x1, y1, x2, y2) or check(x2, y2, x3, y3) or check(x3, y3, x1, y1):
		print('YES')
	else:
		print('NO')


import sys

def InputIterator():
	for line in sys.stdin:
		for value in line.split():
			yield value

def sgn(a):
	return 1 if a > 0 else -1

def intersect(R, x1, y1, x2, y2):
	if x1 * x1 + y1 * y1 == R * R:
		return True
	if x2 * x2 + y2 * y2 == R * R:
		return True
	if x1 * x1 + y1 * y1 < R * R and x2 * x2 + y2 * y2 < R * R:
		return False
	if x1 * x1 + y1 * y1 < R * R and x2 * x2 + y2 * y2 > R * R:
		return True
	if x1 * x1 + y1 * y1 > R * R and x2 * x2 + y2 * y2 < R * R:
		return True
	(a, b) = (y2 - y1, x1 - x2)
	c = -(a * x1) - b * y1
	if c * c > R * R * (a * a + b * b):
		return False
	return sgn(b * x1 - a * y1) != sgn(b * x2 - a * y2)
inp = InputIterator()
T = int(next(inp))
for t in range(T):
	(xc, yc, R) = (int(next(inp)), int(next(inp)), int(next(inp)))
	(x1, y1) = (int(next(inp)), int(next(inp)))
	(x2, y2) = (int(next(inp)), int(next(inp)))
	(x3, y3) = (int(next(inp)), int(next(inp)))
	if intersect(R, x1 - xc, y1 - yc, x2 - xc, y2 - yc) or intersect(R, x2 - xc, y2 - yc, x3 - xc, y3 - yc) or intersect(R, x3 - xc, y3 - yc, x1 - xc, y1 - yc):
		print('YES')
	else:
		print('NO')


def distToSegment(x1, y1, x2, y2, x3, y3):
	px = x2 - x1
	py = y2 - y1
	something = px * px + py * py
	u = ((x3 - x1) * px + (y3 - y1) * py) / float(something)
	if u > 1:
		u = 1
	elif u < 0:
		u = 0
	x = x1 + u * px
	y = y1 + u * py
	dx = x - x3
	dy = y - y3
	dist = dx * dx + dy * dy
	return dist

def isInsideCircle(xc, yc, r, x, y):
	dx = xc - x
	dy = yc - y
	sqDist = dx * dx + dy * dy
	return sqDist <= r ** 2

def isOutsideCircle(xc, yc, r, x, y):
	dx = xc - x
	dy = yc - y
	sqDist = dx * dx + dy * dy
	return sqDist >= r ** 2

def solve(xc, yc, r, x1, y1, x2, y2, x3, y3):
	nbInside = 0
	if isInsideCircle(xc, yc, r, x1, y1):
		nbInside += 1
	if isInsideCircle(xc, yc, r, x2, y2):
		nbInside += 1
	if isInsideCircle(xc, yc, r, x3, y3):
		nbInside += 1
	nbOutside = 0
	if isOutsideCircle(xc, yc, r, x1, y1):
		nbOutside += 1
	if isOutsideCircle(xc, yc, r, x2, y2):
		nbOutside += 1
	if isOutsideCircle(xc, yc, r, x3, y3):
		nbOutside += 1
	if not (nbInside == 3 and nbOutside == 0 or (nbInside == 0 and nbOutside == 3)):
		return True
	if nbInside == 3 and nbOutside == 0:
		return False
	else:
		sqR = r ** 2
		if distToSegment(x1, y1, x2, y2, xc, yc) <= sqR:
			return True
		if distToSegment(x1, y1, x3, y3, xc, yc) <= sqR:
			return True
		if distToSegment(x2, y2, x3, y3, xc, yc) <= sqR:
			return True
		return False
T = int(input())
for _ in range(T):
	(xc, yc, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	if solve(xc, yc, r, x1, y1, x2, y2, x3, y3):
		print('YES')
	else:
		print('NO')


from math import sqrt
eps = 1e-09

def equal(x, y):
	return abs(x - y) < eps

def less(x, y):
	return x + eps < y

class Point:
	x = 1000
	y = 1000

	def read(self):
		[self.x, self.y] = [float(a) for a in input().split(' ')]

def sq(x):
	return x * x

def distance(a, b):
	return sqrt(sq(a.x - b.x) + sq(a.y - b.y))

def area(a, b, c):
	return abs((a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x)) / 2
t = int(input())
c = Point()
triangle = [Point() for x in range(3)]
for i in range(t):
	ans = False
	[c.x, c.y, r] = [float(a) for a in input().split(' ')]
	for i in range(3):
		triangle[i].read()
	inside = 0
	for i in range(3):
		if less(distance(triangle[i], c), r):
			inside += 1
		if equal(distance(triangle[i], c), r):
			ans = True
	if ans:
		print('YES')
		continue
	if 0 < inside and inside < 3:
		print('YES')
		continue
	if inside == 3:
		print('NO')
		continue
	ans = False
	for i in range(3):
		a = triangle[i]
		b = triangle[(i + 1) % 3]
		dist = distance(a, b)
		h = 2 * area(c, a, b) / dist
		le = sqrt(sq(distance(c, a)) - sq(h))
		re = sqrt(sq(distance(c, b)) - sq(h))
		if less(dist, le + re):
			continue
		if less(h, r) or equal(h, r):
			ans = True
	if ans:
		print('YES')
	else:
		print('NO')


import math

def intersect(cx, cy, r, x1, y1, x2, y2):
	threshold = 0.0001
	dx = x2 - x1
	dy = y2 - y1
	t = math.sqrt(dx ** 2 + dy ** 2)
	(dx, dy) = (dx / t, dy / t)
	t2 = (dx * (cy - y1) - dy * (cx - x1)) / (dx ** 2 + dy ** 2)
	ix = cx + t2 * dy
	iy = cy - t2 * dx
	ri = math.sqrt((ix - cx) ** 2 + (iy - cy) ** 2)
	if ri > r + threshold:
		return False
	if abs(ri - r) < threshold:
		return True
	b = math.sqrt(r * r - ri * ri)
	mx1 = ix + b * dx
	my1 = iy + b * dy
	mx2 = ix - b * dx
	my2 = iy - b * dy
	maxx = max(x1, x2)
	minx = min(x1, x2)
	maxy = max(y1, y2)
	miny = min(y1, y2)
	return minx - threshold <= mx1 <= maxx + threshold and miny - threshold <= my1 <= maxy + threshold or (minx - threshold <= mx2 <= maxx + threshold and miny - threshold <= my2 <= maxy + threshold)
for _ in range(0, int(input())):
	circle = [int(x) for x in input().split(' ')]
	v = []
	for i in range(0, 3):
		v.append([int(x) for x in input().split(' ')])
	print('YES' if intersect(*circle + v[0] + v[1]) or intersect(*circle + v[1] + v[2]) or intersect(*circle + v[0] + v[2]) else 'NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


def per(c, a, b):
	d = abs(((b[0] - a[0]) * c[1] - (b[1] - a[1]) * c[0] + (a[0] * b[1] - a[1] * b[0])) / pow(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2), 1 / 2))
	if d > c[2]:
		return False
	else:
		return poi(c, a, b)

def poi(c, a, b):
	if a[1] != b[1]:
		d = -((b[0] - a[0]) / (b[1] - a[1]))
		e = a[1] - d * a[0] - (c[1] - d * c[0]) > 0
		f = b[1] - d * b[0] - (c[1] - d * c[0]) > 0
		if e == f:
			return False
		else:
			return True
	else:
		e = a[0] - c[0] > 0
		f = b[0] - c[0] > 0
		if e == f:
			return False
		else:
			return True

def cir(c, a):
	y = pow(a[0] - c[0], 2) + pow(a[1] - c[1], 2) - pow(c[2], 2)
	if y > 0:
		return 1
	elif y == 0:
		return 2
	else:
		return 0
a = int(input())
for b in range(a):
	c = list((i for i in map(int, input().split(' '))))
	x = list((i for i in map(int, input().split(' '))))
	y = list((i for i in map(int, input().split(' '))))
	z = list((i for i in map(int, input().split(' '))))
	x1 = cir(c, x)
	y1 = cir(c, y)
	z1 = cir(c, z)
	if x1 == 2 or y1 == 2 or z1 == 2:
		print('YES')
	elif x1 == 0 and y1 == 0 and (z1 == 0):
		print('NO')
	elif x1 != y1 or y1 != z1 or x1 != z1:
		print('YES')
	elif per(c, x, y) or per(c, x, z) or per(c, z, y):
		print('YES')
	else:
		print('NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


import sys
from math import sqrt
source = sys.stdin

def disc(R, x1, y1, x2, y2):
	d = 2 * x1 * y1 * (x2 - x1) * (y2 - y1)
	d += (R * R - y1 * y1) * (x2 - x1) ** 2
	d += (R * R - x1 * x1) * (y2 - y1) ** 2
	return d

def intersects(R, u, v):
	[x1, y1] = u
	[x2, y2] = v
	d = disc(R, x1, y1, x2, y2)
	if d < 0:
		return False
	else:
		a = -1 * (x1 * (x2 - x1) + y1 * (y2 - y1))
		b = sqrt(d)
		g = (x2 - x1) ** 2 + (y2 - y1) ** 2
		c1 = (a + b) / g
		c2 = (a - b) / g
		if c1 >= 0 and c1 <= 1:
			return True
		if c2 >= 0 and c2 <= 1:
			return True
		return False
T = int(source.readline())
for _ in range(T):
	[xc, yc, R] = [int(s) for s in source.readline().split()]
	c = [xc, yc]
	v0 = [int(s) for s in source.readline().split()]
	v1 = [int(s) for s in source.readline().split()]
	v2 = [int(s) for s in source.readline().split()]
	v0 = [a - b for (a, b) in zip(v0, c)]
	v1 = [a - b for (a, b) in zip(v1, c)]
	v2 = [a - b for (a, b) in zip(v2, c)]
	does_intersect = intersects(R, v0, v1) or intersects(R, v0, v2) or intersects(R, v1, v2)
	if does_intersect:
		print('YES')
	else:
		print('NO')


import sys
t = int(input().strip())
for o in range(t):
	n = input().strip().split(' ')
	x0 = int(n[0])
	y0 = int(n[1])
	r = int(n[2])
	n = input().strip().split(' ')
	x1 = int(n[0])
	y1 = int(n[1])
	n = input().strip().split(' ')
	x2 = int(n[0])
	y2 = int(n[1])
	n = input().strip().split(' ')
	x3 = int(n[0])
	y3 = int(n[1])
	if (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) - r * r < 0 and (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0) - r * r < 0 and ((x3 - x0) * (x3 - x0) + (y3 - y0) * (y3 - y0) - r * r < 0):
		print('NO')
	elif (x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0) - r * r <= 0 or (x2 - x0) * (x2 - x0) + (y2 - y0) * (y2 - y0) - r * r <= 0 or (x3 - x0) * (x3 - x0) + (y3 - y0) * (y3 - y0) - r * r <= 0:
		print('YES')
	else:
		l = [[x1, y1], [x2, y2], [x3, y3], [x1, y1]]
		flag = 0
		for p in range(3):
			if flag == 0:
				xx1 = l[p][0]
				yy1 = l[p][1]
				xx2 = l[p + 1][0]
				yy2 = l[p + 1][1]
				if xx2 != xx1:
					m = (yy2 - yy1) / (xx2 - xx1)
					c = yy1 - m * xx1
					xx1_2 = (x0 + m * y0 - m * c) / (1 + m * m)
					yy1_2 = (m * x0 - m * m * y0 + c) / (1 + m * m)
					dis = abs((-1 * m * x0 + y0 - c) / (1 + m * m) ** 0.5)
					if (xx1 >= xx1_2 >= xx2 or xx1 <= xx1_2 <= xx2) and (yy1 >= yy1_2 >= yy2 or yy1 <= yy1_2 <= yy2) and (dis <= r):
						print('YES')
						flag = 1
				elif (yy1 >= y0 >= yy2 or yy1 <= y0 <= yy2) and (xx1 - x0) * (xx1 - x0) - r * r <= 0:
					print('YES')
					flag = 1
		if flag == 0:
			print('NO')


from fractions import Fraction

def get_linear_solution(p, P):
	det = p[0] * P[1] - p[1] * P[0]
	return (Fraction(-p[2] * P[1] + P[2] * p[1], det), Fraction(-(-p[2] * P[0] + P[2] * p[0]), det))

def point_in_segment(p, s1, s2):
	if s1[0] <= p[0] <= s2[0] or s2[0] <= p[0] <= s1[0]:
		if s1[1] <= p[1] <= s2[1] or s2[1] <= p[1] <= s1[1]:
			if (p[1] - s1[1]) * (s2[0] - s1[0]) == (p[0] - s1[0]) * (s2[1] - s1[1]):
				return True
	return False
T = int(input())
for t in range(T):
	(xc, yc, R) = list(map(int, input().split()))
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	RR = R ** 2
	D = ((x1 - xc) ** 2 + (y1 - yc) ** 2, (x2 - xc) ** 2 + (y2 - yc) ** 2, (x3 - xc) ** 2 + (y3 - yc) ** 2)
	if max(D) < RR:
		print('NO')
	elif min(D) > RR:
		common_point = False
		p12 = (y2 - y1, -(x2 - x1), y1 * x2 - y2 * x1)
		p12_ = (x2 - x1, y2 - y1, -xc * (x2 - x1) - yc * (y2 - y1))
		p = get_linear_solution(p12, p12_)
		if (p[0] - xc) ** 2 + (p[1] - yc) ** 2 <= RR:
			if point_in_segment(p, (x1, y1), (x2, y2)):
				common_point = True
		if not common_point:
			p13 = (y3 - y1, -(x3 - x1), y1 * x3 - y3 * x1)
			p13_ = (x3 - x1, y3 - y1, -xc * (x3 - x1) - yc * (y3 - y1))
			p = get_linear_solution(p13, p13_)
			if (p[0] - xc) ** 2 + (p[1] - yc) ** 2 <= RR:
				if point_in_segment(p, (x1, y1), (x3, y3)):
					common_point = True
		if not common_point:
			p23 = (y3 - y2, -(x3 - x2), y2 * x3 - y3 * x2)
			p23_ = (x3 - x2, y3 - y2, -xc * (x3 - x2) - yc * (y3 - y2))
			p = get_linear_solution(p23, p23_)
			if (p[0] - xc) ** 2 + (p[1] - yc) ** 2 <= RR:
				if point_in_segment(p, (x2, y2), (x3, y3)):
					common_point = True
		if common_point:
			print('YES')
		else:
			print('NO')
	else:
		print('YES')


def dotprod(a, b):
	return sum((i * j for (i, j) in zip(a, b)))

def intersect(xc, yc, r, x1, y1, x2, y2):
	s = (x2 - x1, y2 - y1)
	t = (x1 - xc, y1 - yc)
	a = dotprod(s, s)
	b = 2 * dotprod(s, t)
	c = dotprod(t, t) - r * r
	disc = b * b - 4 * a * c
	if disc < 0:
		return False
	else:
		disc = disc ** 0.5
		r1 = (-b - disc) / (2 * a)
		r2 = (-b + disc) / (2 * a)
		if 0 <= r1 <= 1 or 0 <= r2 <= 1:
			return True
		else:
			return False
for _ in range(int(input())):
	(xc, yc, r) = [int(a) for a in input().split()]
	(x1, y1) = [int(a) for a in input().split()]
	(x2, y2) = [int(a) for a in input().split()]
	(x3, y3) = [int(a) for a in input().split()]
	if intersect(xc, yc, r, x1, y1, x2, y2) or intersect(xc, yc, r, x2, y2, x3, y3) or intersect(xc, yc, r, x3, y3, x1, y1):
		print('YES')
	else:
		print('NO')


def isTouching(A, B, C, r):
	(ax, ay) = A
	(bx, by) = B
	(cx, cy) = C
	(vx, vy) = (bx - ax, by - ay)
	(wx, wy) = (ax - cx, ay - cy)
	(a, b, c) = (vx * vx + vy * vy, 2 * (vx * wx + vy * wy), wx * wx + wy * wy - r * r)
	d = b * b - 4 * a * c
	if d < 0:
		return False
	t0 = (-b - d ** 0.5) / (2 * a)
	if 0 <= t0 <= 1:
		return True
	t1 = (-b + d ** 0.5) / (2 * a)
	if 0 <= t1 <= 1:
		return True
T = int(input())
for _ in range(T):
	(ox, oy, r) = map(int, input().split())
	(ax, ay) = map(int, input().split())
	(bx, by) = map(int, input().split())
	(cx, cy) = map(int, input().split())
	if isTouching((ax, ay), (bx, by), (ox, oy), r) or isTouching((bx, by), (cx, cy), (ox, oy), r) or isTouching((cx, cy), (ax, ay), (ox, oy), r):
		print('YES')
	else:
		print('NO')


from fractions import Fraction

def check(pts, R2):
	inside = 0
	for (x, y) in pts:
		d = x * x + y * y
		if d == R2:
			return True
		elif d < R2:
			inside += 1
	if inside == 3:
		return False
	if inside:
		return True
	for i in range(3):
		(x, y) = pts[i]
		(x2, y2) = pts[(i + 1) % 3]
		dx = x - x2
		dy = y - y2
		t = Fraction(x * dx + y * dy, dx * dx + dy * dy)
		if t > 0 and t < 1:
			xp = x - t * dx
			yp = y - t * dy
			if xp * xp + yp * yp <= R2:
				return True
	return False
T = int(input())
for t in range(T):
	(xc, yc, R) = map(int, input().split())
	pts = []
	for i in range(3):
		(x, y) = map(int, input().split())
		pts.append((x - xc, y - yc))
	print('YES' if check(pts, R * R) else 'NO')


import logging
import math

def normalize(v):
	l = 0
	for x in v:
		l += x ** 2
	l = math.sqrt(l)
	for i in range(len(v)):
		v[i] /= l
	return v

def sp(x, y):
	scalar_product = 0
	for (i, j) in zip(x, y):
		scalar_product += i * j
	return scalar_product

def check_intersection(p_0, p_1, c, r):
	logging.debug('checking points %s and %s and circle %s, %s', p_0, p_1, c, r)
	inside = False
	outside = False
	for p in [p_0, p_1]:
		d = (p[0] - c[0]) ** 2 + (p[1] - c[1]) ** 2
		if d == r ** 2:
			logging.debug('point on circle')
			return True
		elif d < r ** 2:
			inside = True
		else:
			outside = True
	if not outside:
		logging.debug('both inside')
		return False
	if inside:
		logging.debug('one inside, one outside')
		return True
	logging.debug('both outside')
	v = [p_0[0] - p_1[0], p_0[1] - p_1[1]]
	n = normalize([v[1], -v[0]])
	d = abs(sp(n, c) - sp(n, p_0))
	if d <= r:
		logging.debug('the infite line touches/intersects')
		if sp(v, p_0) <= sp(v, c) and sp(v, c) <= sp(v, p_1):
			return True
		if sp(v, p_0) >= sp(v, c) and sp(v, c) >= sp(v, p_1):
			return True
	logging.debug('No segment intersection')
	return False
T = int(input())
x = [0, 0, 0]
y = [0, 0, 0]
c = [0, 0]
for _ in range(T):
	(c[0], c[1], r) = (int(z) for z in input().split())
	(x[0], y[0]) = (int(z) for z in input().split())
	(x[1], y[1]) = (int(z) for z in input().split())
	(x[2], y[2]) = (int(z) for z in input().split())
	c_1 = check_intersection([x[0], y[0]], [x[1], y[1]], c, r)
	c_2 = check_intersection([x[0], y[0]], [x[2], y[2]], c, r)
	c_3 = check_intersection([x[1], y[1]], [x[2], y[2]], c, r)
	if c_1 or c_2 or c_3:
		print('YES')
	else:
		print('NO')


import sys

def intersect(c, r, p1, p2):
	(cx, cy) = c
	(x1, y1) = p1
	(x2, y2) = p2
	a = pow(x1 - x2, 2) + pow(y1 - y2, 2)
	b = 2 * ((x1 - x2) * (x2 - cx) + (y1 - y2) * (y2 - cy))
	c = pow(x2 - cx, 2) + pow(y2 - cy, 2) - pow(r, 2)
	if a == 0:
		if b == 0:
			return c == 0
		t = -c / b
		return t >= 0 and t <= 1
	D = b * b - 4 * a * c
	if D < 0:
		return False
	rD = pow(D, 0.5)
	t1 = (-b - rD) / (2 * a)
	t2 = (-b + rD) / (2 * a)
	if t1 >= 0 and t1 <= 1:
		return True
	if t2 >= 0 and t2 <= 1:
		return True
	return False

def solve(c, r, tr):
	return intersect(c, r, tr[0], tr[1]) or intersect(c, r, tr[1], tr[2]) or intersect(c, r, tr[2], tr[0])
t = int(input())
for _ in range(t):
	(cx, cy, r) = map(int, input().split())
	p1 = tuple(map(int, input().split()))
	p2 = tuple(map(int, input().split()))
	p3 = tuple(map(int, input().split()))
	if solve((cx, cy), r, (p1, p2, p3)):
		print('YES')
	else:
		print('NO')


def circle_segment_intersect(xc, yc, R, x1, y1, x2, y2):
	R2 = R * R
	R21 = (x1 - xc) ** 2 + (y1 - yc) ** 2
	R22 = (x2 - xc) ** 2 + (y2 - yc) ** 2
	if R21 < R2 and R22 < R2:
		return False
	if R21 <= R2 or R22 <= R2:
		return True
	(nx, ny) = (-(y2 - y1), x2 - x1)
	n2 = nx * nx + ny * ny
	det1 = (x1 - xc) * ny - (y1 - yc) * nx
	det2 = (x2 - xc) * ny - (y2 - yc) * nx
	if det1 * det2 >= 0:
		return False
	a2 = ((x1 - xc) * nx + (y1 - yc) * ny) ** 2
	return a2 <= R2 * n2

def svg_draw(fname, xc, yc, R, x1, y1, x2, y2, x3, y3):
	mx = min([xc - R, x1, x2, x3])
	Mx = max([xc + R, x1, x2, x3])
	my = min([yc - R, y1, y2, y3])
	My = max([yc + R, y1, y2, y3])
	OPT = 'fill="none" stroke="black" stroke-width="0.5"'
	f = open(fname, 'w')
	f.write('<svg width="%d" height="%d">\n' % (Mx - mx, My - my))
	f.write('<circle cx="%d" cy="%d" r="%d" %s />\n' % (xc - mx, yc - my, R, OPT))
	f.write('<path d="M%d %d L%d %d L%d %d Z" %s />\n' % (x1 - mx, y1 - my, x2 - mx, y2 - my, x3 - mx, y3 - my, OPT))
	f.write('</svg>')
	f.close()

def main():
	T = int(input())
	for t in range(T):
		(xc, yc, R) = map(int, input().split())
		(x1, y1) = map(int, input().split())
		(x2, y2) = map(int, input().split())
		(x3, y3) = map(int, input().split())
		intersect = circle_segment_intersect(xc, yc, R, x1, y1, x2, y2) or circle_segment_intersect(xc, yc, R, x1, y1, x3, y3) or circle_segment_intersect(xc, yc, R, x3, y3, x2, y2)
		print('YES' if intersect else 'NO')
main()


t = int(input())
for i in range(0, t):
	(xc, yc, r) = list(map(int, input().split()))
	L = []
	L.append(list(map(int, input().split(' '))))
	L.append(list(map(int, input().split(' '))))
	L.append(list(map(int, input().split(' '))))

	def dist(x1, y1, x2, y2):
		return ((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) ** 0.5
	flag = 0
	length = []
	for i in range(0, 3):
		length.append(dist(L[i][0], L[i][1], xc, yc))
	for i in range(0, 2):
		for j in range(i + 1, 3):
			x1 = L[i][0]
			y1 = L[i][1]
			x2 = L[j][0]
			y2 = L[j][1]
			s0 = dist(x1, y1, x2, y2)
			s1 = dist(xc, yc, x1, y1)
			s2 = dist(xc, yc, x2, y2)
			height = abs(x2 * y1 + xc * y2 + x1 * yc - (x1 * y2 + x2 * yc + xc * y1)) / s0
			if s1 <= r or s2 <= r:
				flag = 1
			elif height <= r:
				if ((y1 - yc) * (y2 - y1) + (x1 - xc) * (x2 - x1)) * ((y2 - yc) * (y2 - y1) + (x2 - xc) * (x2 - x1)) <= 0:
					flag = 1
	(a, b, c) = length
	if a < r and b < r and (c < r):
		flag = 0
	if flag == 1:
		print('YES')
	else:
		print('NO')


import os
import sys

def inside(t, c):
	[x, y, r] = c
	[a, b] = t
	if (x - a) ** 2 + (y - b) ** 2 == r ** 2:
		return 'it touches'
	return (x - a) ** 2 + (y - b) ** 2 <= r ** 2

def cut(t1, t2, c):
	[x, y, r] = c
	[x1, y1] = t1
	[x2, y2] = t2
	t = -((x2 - x1) * (x1 - x) + (y2 - y1) * (y1 - y)) / ((x2 - x1) ** 2 + (y2 - y1) ** 2)
	t = min(t, 1)
	t = max(t, 0)
	i = inside([x1 + t * (x2 - x1), y1 + t * (y2 - y1)], c)
	if i == 'it touches':
		return True
	return i

def solve(c, t1, t2, t3):
	x1 = inside(t1, c)
	x2 = inside(t2, c)
	x3 = inside(t3, c)
	if x1 == 'it touches' or x2 == 'it touches' or x3 == 'it touches':
		return 'YES'
	if (x1 == x2) & (x2 == x3):
		if x1:
			return 'NO'
		else:
			if cut(t1, t2, c) or cut(t1, t3, c) or cut(t3, t2, c):
				return 'YES'
			return 'NO'
	else:
		return 'YES'
t = int(input())
for _ in range(t):
	c = list(map(float, input().strip().split()))
	t1 = list(map(float, input().strip().split()))
	t2 = list(map(float, input().strip().split()))
	t3 = list(map(float, input().strip().split()))
	print(solve(c, t1, t2, t3))


from decimal import *

def check_dots(dot1, dot2, check):
	if dot1[0] > dot2[0]:
		(dot1, dot2) = (dot2, dot1)
	(minx, maxx) = (dot1[0], dot2[0])
	if dot1[1] > dot2[1]:
		(dot1, dot2) = (dot2, dot1)
	(miny, maxy) = (dot1[1], dot2[1])
	return minx <= check[0] <= maxx and miny <= check[1] <= maxy

def find_interseption(x, y, r, dot1, dot2):
	result = False
	if dot1[0] != dot2[0]:
		k = (dot2[1] - dot1[1]) / (dot2[0] - dot1[0])
		b = dot1[1] - k * dot1[0]
		D = 4 * r ** 2 * (k ** 2 + 1) - 4 * (k * x + b - y) ** 2
		if D >= 0:
			x1 = ((k * (b - y) - x) * -2 + D.sqrt()) / (2 * (k ** 2 + 1))
			y1 = k * x1 + b
			x2 = (-2 * (k * (b - y) - x) - D.sqrt()) / (2 * (k ** 2 + 1))
			y2 = k * x2 + b
			answ = [[x1, y1], [x2, y2]]
			for j in range(2):
				if check_dots(dot1, dot2, answ[j]):
					result = True
	else:
		D = (r - dot1[0] + x) * (r + dot1[0] - x)
		if D >= 0:
			answ = [[dot1[0], D.sqrt() + y], [dot1[0], D.sqrt() * -1 + y]]
			for j in range(2):
				if check_dots(dot1, dot2, answ[j]):
					result = True
	return result
res = []
for _ in range(int(input())):
	result = False
	(x, y, r) = [Decimal(el) for el in input().split()]
	dots = []
	rs = []
	for j in range(3):
		dots.append([Decimal(el) for el in input().split()])
		if (x - dots[j][0]) ** 2 + (y - dots[j][1]) ** 2 - r ** 2 == 0:
			rs.append(True)
	if len(rs):
		result = True
	else:
		(inner, outter) = ([], [])
		for j in range(3):
			if (dots[j][0] - x) ** 2 + (dots[j][1] - y) ** 2 < r ** 2:
				inner.append(dots[j])
			else:
				outter.append(dots[j])
		if len(inner) == 3:
			pass
		elif len(inner) >= 1 and len(outter) >= 1:
			result = True
		else:
			dots.append(dots[0])
			for i in range(3):
				if find_interseption(x, y, r, dots[i], dots[i + 1]):
					result = True
	res.append(result)
for el in res:
	if el:
		print('YES')
	else:
		print('NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')


from fractions import Fraction as F
t = int(input())

def check(x1, y1, x2, y2, r):
	(x, y) = (x1, y1)
	dx = x2 - x
	dy = y2 - y
	A = dx ** 2 + dy ** 2
	halfB = x * dx + y * dy
	opt = F(-halfB, A)
	if opt < 0:
		opt = 0
	elif opt > 1:
		opt = 1
	least_dist = (x + dx * opt) ** 2 + (y + dy * opt) ** 2
	max_dist = max(x1 ** 2 + y1 ** 2, x2 ** 2 + y2 ** 2)
	return least_dist <= r ** 2 <= max_dist
for _ in range(t):
	(x0, y0, r) = map(int, input().split())
	(x1, y1) = map(int, input().split())
	(x2, y2) = map(int, input().split())
	(x3, y3) = map(int, input().split())
	x1 -= x0
	y1 -= y0
	x2 -= x0
	y2 -= y0
	x3 -= x0
	y3 -= y0
	print('YES' if check(x1, y1, x2, y2, r) or check(x2, y2, x3, y3, r) or check(x3, y3, x1, y1, r) else 'NO')