#944112 (PyPy3) No.2602 Real Collider

提出ソース

結果

問題	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	45 ms 54,528 KB
testcase_01	AC	42 ms 54,528 KB
testcase_02	AC	41 ms 54,400 KB
testcase_03	AC	45 ms 55,168 KB
testcase_04	WA	-
testcase_05	WA	-
testcase_06	AC	42 ms 54,656 KB
testcase_07	AC	43 ms 54,528 KB
testcase_08	WA	-
testcase_09	AC	43 ms 55,964 KB
testcase_10	AC	441 ms 77,312 KB
testcase_11	WA	-
testcase_12	AC	262 ms 77,056 KB
testcase_13	AC	163 ms 77,056 KB
testcase_14	WA	-
testcase_15	AC	190 ms 77,056 KB
testcase_16	WA	-
testcase_17	AC	265 ms 77,312 KB
testcase_18	AC	207 ms 76,672 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	AC	204 ms 77,056 KB
testcase_22	AC	244 ms 77,184 KB
testcase_23	AC	188 ms 77,500 KB
testcase_24	AC	228 ms 76,928 KB
testcase_25	AC	222 ms 77,184 KB
testcase_26	AC	244 ms 77,476 KB
testcase_27	AC	267 ms 77,104 KB
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	273 ms 77,388 KB
testcase_32	AC	232 ms 77,056 KB
testcase_33	AC	271 ms 77,592 KB
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	AC	261 ms 77,056 KB
testcase_38	AC	272 ms 77,056 KB
testcase_39	WA	-
testcase_40	WA	-
testcase_41	AC	283 ms 76,672 KB
testcase_42	AC	246 ms 77,056 KB
testcase_43	AC	243 ms 77,056 KB
testcase_44	AC	288 ms 77,056 KB
testcase_45	WA	-
testcase_46	WA	-
testcase_47	AC	292 ms 77,616 KB
testcase_48	WA	-
testcase_49	AC	202 ms 76,928 KB
testcase_50	WA	-
testcase_51	AC	188 ms 77,504 KB
testcase_52	AC	161 ms 77,184 KB
testcase_53	AC	273 ms 77,100 KB
testcase_54	AC	214 ms 77,312 KB
testcase_55	AC	226 ms 77,312 KB
testcase_56	AC	234 ms 77,176 KB
testcase_57	AC	221 ms 77,184 KB
testcase_58	AC	148 ms 77,648 KB
testcase_59	WA	-
testcase_60	WA	-
testcase_61	WA	-
testcase_62	WA	-
testcase_63	WA	-
testcase_64	WA	-
testcase_65	WA	-
testcase_66	WA	-
testcase_67	AC	178 ms 76,800 KB
testcase_68	WA	-
testcase_69	WA	-
testcase_70	WA	-
testcase_71	WA	-
testcase_72	WA	-
testcase_73	WA	-
testcase_74	WA	-
testcase_75	WA	-
testcase_76	WA	-
testcase_77	WA	-
testcase_78	AC	292 ms 77,180 KB
testcase_79	WA	-
testcase_80	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

# 最小含有円を求めるコード、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')

yukicoder

結果

テストケース

ソースコード