結果

問題 No.2602 Real Collider
ユーザー FromBooska
提出日時 2024-01-13 21:52:19
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,995 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 78,252 KB
最終ジャッジ日時 2024-09-28 01:48:01
合計ジャッジ時間 20,545 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38 WA * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

# 最小含有円を求めるコード、Minimum enclosing circle using Welzl’s algorithm
# https://www.geeksforgeeks.org/minimum-enclosing-circle-using-welzls-algorithm/

# Python3 program to find the minimum enclosing
# circle for N integer points in a 2-D plane
from math import sqrt
from random import randint,shuffle

# Defining infinity
INF = 1e18

# Structure to represent a 2D point
class Point :
	def __init__(self,X=0,Y=0) -> None:
		self.X=X
		self.Y=Y

# Structure to represent a 2D circle
class Circle :
	def __init__(self,c=Point(),r=0) -> None:	 
		self.C=c
		self.R=r

# Function to return the euclidean distance
# between two points
def dist(a, b):
	return sqrt(pow(a.X - b.X, 2)
				+ pow(a.Y - b.Y, 2))

# Function to check whether a point lies inside
# or on the boundaries of the circle
def is_inside(c, p):
	return dist(c.C, p) <= c.R

# The following two functions are used
# To find the equation of the circle when
# three points are given.

# Helper method to get a circle defined by 3 points
def get_circle_center(bx, by, cx, cy):
	B = bx * bx + by * by
	C = cx * cx + cy * cy
	D = bx * cy - by * cx
	return Point((cy * B - by * C) / (2 * D),
			(bx * C - cx * B) / (2 * D))

# Function to return the smallest circle
# that intersects 2 points
def circle_from1(A, B):
	# Set the center to be the midpoint of A and B
	C = Point((A.X + B.X) / 2.0, (A.Y + B.Y) / 2.0 )

	# Set the radius to be half the distance AB
	return Circle(C, dist(A, B) / 2.0 )

# Function to return a unique circle that intersects three points
def circle_from2(A, B, C):
	I = get_circle_center(B.X - A.X, B.Y - A.Y, C.X - A.X, C.Y - A.Y)
	I.X += A.X
	I.Y += A.Y
	return Circle(I, dist(I, A))

# Function to check whether a circle encloses the given points
def is_valid_circle(c, P):
	# Iterating through all the points
	# to check whether the points
	# lie inside the circle or not
	for p in P:
		if (not is_inside(c, p)):
			return False
	return True

# Function to return the minimum enclosing circle for N <= 3
def min_circle_trivial(P):
	assert(len(P) <= 3)
	if not P :
		return Circle() 
	
	elif (len(P) == 1) :
		return Circle(P[0], 0) 
	
	elif (len(P) == 2) :
		return circle_from1(P[0], P[1])

	# To check if MEC can be determined
	# by 2 points only
	for i in range(3):
		for j in range(i + 1,3):

			c = circle_from1(P[i], P[j])
			if (is_valid_circle(c, P)):
				return c
	
	return circle_from2(P[0], P[1], P[2])

# Returns the MEC using Welzl's algorithm
# Takes a set of input points P and a set R
# points on the circle boundary.
# n represents the number of points in P
# that are not yet processed.
def welzl_helper(P, R, n):
	# Base case when all points processed or |R| = 3
	if (n == 0 or len(R) == 3) :
		return min_circle_trivial(R)

	# Pick a random point randomly
	idx = randint(0,n-1)
	p = P[idx]

	# Put the picked point at the end of P
	# since it's more efficient than
	# deleting from the middle of the vector
	P[idx], P[n - 1]=P[n-1],P[idx]

	# Get the MEC circle d from the
	# set of points P - :p
	d = welzl_helper(P, R.copy(), n - 1)

	# If d contains p, return d
	if (is_inside(d, p)) :
		return d

	# Otherwise, must be on the boundary of the MEC
	R.append(p)

	# Return the MEC for P - :p and R U :p
	return welzl_helper(P, R.copy(), n - 1)

def welzl(P):
	P_copy = P.copy()
	shuffle(P_copy)
	return welzl_helper(P_copy, [], len(P_copy))

'''
# Driver code
if __name__ == '__main__':
	mec = welzl([Point(0, 0), Point(0, 1), Point(1, 0) ])
	print("Center = {",mec.C.X,",", mec.C.Y,"} Radius =",mec.R)

	mec2 = welzl([Point(5, -2), Point(-3, -2), Point(-2, 5), Point(1, 6), Point(0, 2)] )
	print("Center = {",mec2.C.X,",",mec2.C.Y,"} Radius =",mec2.R)
'''

    
Q = int(input())
x1, y1, x2, y2, x3, y3 = map(int, input().split())
mec = welzl([Point(x1, y1), Point(x2, y2), Point(x3, y3) ])

points = []
for i in range(Q):
    x, y = map(int, input().split())
    if (x-mec.C.X)**2+(y-mec.C.Y)**2 <= mec.R**2:
        print('Yes')
    else:
        print('No')
0