コンテンツにスキップ

Blitz Round #25 E - Circles are POINTS !

サイト
Eolymp
コンテスト
Blitz Round #25
問題
E - Circles are POINTS !

平面上の nn 個の格子点からなる集合があり、そのうち 2 点は base point と呼ばれます。次の 2 種類のクエリを qq 回処理します。

  • 点 (x,y)(x, y) を集合に追加する(まだ集合にない点)
  • 点 (x,y)(x, y) を集合から削除する(集合にあり、base point ではない点)

最初の状態と各クエリの後に、集合のすべての点を通る円が描けるかを判定する問題です。

  • 2≤n≤2⋅1052 \le n \le 2 \cdot 10^5、0≤q≤2⋅1050 \le q \le 2 \cdot 10^5、∣x∣,∣y∣≤106|x|, |y| \le 10^6、テストケースの nn の総和と qq の総和はそれぞれ 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

base point を固定して円で分類する

Section titled “base point を固定して円で分類する”

base point を A,BA, B とします。A,BA, B は削除されないので常に集合にあり、すべての点を通る円があるなら、それは A,BA, B を通る円です。

base point 以外の点 PP について、

  • PP が直線 ABAB 上にあるなら、異なる 3 点が一直線上に並ぶので円は描けません
  • そうでなければ、A,B,PA, B, P を通る円がただ 1 つ決まります

したがって、答えが YES になるのは「直線 ABAB 上の点がなく、base point 以外のすべての点について A,B,PA, B, P を通る円が同じ」ときです。点を「A,B,PA, B, P を通る円」で分類して、種類が 1 種類以下かを見ればよいことになります。

円の中心の座標で分類すると浮動小数点数の誤差が気になるので、整数だけで計算できる量を使います。

AA を原点に平行移動して u=B−Au = B - A とすると、原点と uu を通る円はすべて、あるパラメータ λ\lambda を使って

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda \, (u \times z)

と書けます(⋅\cdot は内積、×\times は外積 x1y2−y1x2x_1 y_2 - y_1 x_2)。

この形に書ける理由

平面上の円は、ww を定数ベクトル、FF を定数として

∣z∣2+w⋅z+F=0|z|^2 + w \cdot z + F = 0

と書けます(中心 −w/2-w/2、半径の 2 乗 ∣w∣2/4−F|w|^2/4 - F)。

  • 原点を通るので、z=0z = 0 を代入して F=0F = 0
  • uu を通るので、z=uz = u を代入して ∣u∣2+w⋅u=0|u|^2 + w \cdot u = 0

後者について、w=−u+dw = -u + d とおくと

∣u∣2+(−u+d)⋅u=d⋅u=0|u|^2 + (-u + d) \cdot u = d \cdot u = 0

となるので、dd は uu に直交するベクトルです。uu を 90° 回したベクトルを u⊥=(−uy,ux)u^\perp = (-u_y, u_x) とすると、uu に直交するベクトルは u⊥u^\perp の実数倍なので、d=−λ u⊥d = -\lambda\, u^\perp (λ∈R\lambda \in \mathbb{R}) と書けます。よって

w=−u−λ u⊥w = -u - \lambda\, u^\perp

です。これを代入し、u⊥⋅z=uxzy−uyzx=u×zu^\perp \cdot z = u_x z_y - u_y z_x = u \times z を使うと

∣z∣2−z⋅u=λ (u×z)|z|^2 - z \cdot u = \lambda\, (u \times z)

になります。

どの λ\lambda でも w≠0w \ne 0 なので半径の 2 乗 ∣w∣2/4|w|^2/4 は正で、本物の円になります。また、円が決まれば係数 ww が決まり、ww から λ\lambda が決まります。つまり、A,BA, B を通る円と実数 λ\lambda は 1 対 1 に対応します。

z=P−Az = P - A を代入して λ\lambda について解くと

λ=(P−A)⋅(P−B)(B−A)×(P−A)\lambda = \frac{(P - A) \cdot (P - B)}{(B - A) \times (P - A)}

です。円と λ\lambda は 1 対 1 に対応するので、2 点について A,BA, B とそれぞれを通る円が同じであることと、それぞれから求めた λ\lambda が等しいことは同値です。分母が 00 になるのは PP が直線 ABAB 上にあるときです。

λ\lambda は分子・分母とも整数なので、gcd で約分して分母を正にそろえた (分子, 分母) の組を辞書のキーにすれば、誤差なく分類できます。

base point 以外の点のキーの個数を Counter で持ち、追加・削除のたびに増減します。直線 ABAB 上の点はキーを None にしておけば、

  • None がない
  • キーの種類が 1 種類以下

のとき YES です。各点のキーの計算は gcd 1 回なので、座標の範囲を CC として全体で O((n+q)log⁡C)O((n + q) \log C) です。

公式解説も、base point A,BA, B を固定して各点 PP について A,B,PA, B, P を通る円を考える点は同じです。直線 ABAB 上にある点の個数と、A,B,PA, B, P の外接円の中心(外心)の集合を管理し、直線上の点がなく外心がすべて一致するときに YES としています。外心は 2 本の垂直二等分線の交点として計算しています。

Python(upsolve)
from math import gcd
from collections import Counter
for _ in range(int(input())):
n, q, a, b = map(int, input().split())
P = [tuple(map(int, input().split())) for _ in range(n)]
ax, ay = P[a - 1]
bx, by = P[b - 1]
ux, uy = bx - ax, by - ay
def key(x, y):
# λ = (P-A)・(P-B) / (B-A)×(P-A) を約分したもの。直線 AB 上なら None
num = (x - ax) * (x - bx) + (y - ay) * (y - by)
den = ux * (y - ay) - uy * (x - ax)
if den == 0:
return None
if den < 0:
num, den = -num, -den
g = gcd(num, den)
return (num // g, den // g)
cnt = Counter()
for i, (x, y) in enumerate(P):
if i != a - 1 and i != b - 1:
cnt[key(x, y)] += 1
def ok():
return None not in cnt and len(cnt) <= 1
print("YES" if ok() else "NO")
for _ in range(q):
c, x, y = input().split()
x, y = int(x), int(y)
k = key(x, y)
if c == "+":
cnt[k] += 1
else:
cnt[k] -= 1
if cnt[k] == 0:
cnt.pop(k)
print("YES" if ok() else "NO")