yukicoder : No.2602 Real Collider

中ぐらいの難易度が多く良い感じで解けた回。
https://yukicoder.me/problems/no/2603

問題

2次元座標上で3つの点が与えられる。
この3点を含む最小の円を考える。

他の点の座標が与えられるので、その点が円の周または内部にあるかどうか判定せよ。

解法

円の中心の座標を求められれば、あとはそこからの距離を求めるだけである。

最初の3点が鈍角三角形または垂直三角形であれば、長辺が円の直径を成す。
そうでなく鋭角三角形であれば、Editorialに示す公式で中心を求められる。

中心の座標は整数ではなく有理数を取りうるので、浮動小数点を使わず正確に判定していこう。
以下ではPythonのFractionを使って有理数の処理を簡単にしている。
計算回数が多いとTLEするので注意。

from fractions import Fraction
import sys
import math

Q=int(input())
X1,Y1,X2,Y2,X3,Y3=map(Fraction,input().strip().split(" "))
CX=-100000

for i in range(3) :
	if (Y2-Y1)*(Y2-Y1)+(X2-X1)*(X2-X1)+(Y3-Y1)*(Y3-Y1)+(X3-X1)*(X3-X1) <= (Y3-Y2)*(Y3-Y2)+(X3-X2)*(X3-X2):
		CX=(X2+X3)/2
		CY=(Y2+Y3)/2
		break
	X1,X2,X3=X2,X3,X1
	Y1,Y2,Y3=Y2,Y3,Y1

if CX == -100000:
	CX = ((X1*X1+Y1*Y1)*(Y2-Y3)+(X2*X2+Y2*Y2)*(Y3-Y1)+(X3*X3+Y3*Y3)*(Y1-Y2))/(2*((Y2-Y3)*(X1-X2)-(Y1-Y2)*(X2-X3)))
	CY = ((X1*X1+Y1*Y1)*(X2-X3)+(X2*X2+Y2*Y2)*(X3-X1)+(X3*X3+Y3*Y3)*(X1-X2))/(2*((X2-X3)*(Y1-Y2)-(X1-X2)*(Y2-Y3)))

R = (X2-CX)*(X2-CX)+(Y2-CY)*(Y2-CY)
for i in range(Q):
	X,Y=map(Fraction,input().strip().split(" "))
	X-=CX
	Y-=CY
	if X*X+Y*Y <= R:
		print("Yes")
	else:
		print("No")

まとめ

外心の座標を求める公式を知らず、愚直に垂直二等分線の交点求めようとしていた…。