Blitz Round #25 E - Circles are POINTS !
平面上の 個の格子点からなる集合があり、そのうち 2 点は base point と呼ばれます。次の 2 種類のクエリを 回処理します。
- 点 を集合に追加する(まだ集合にない点)
- 点 を集合から削除する(集合にあり、base point ではない点)
最初の状態と各クエリの後に、集合のすべての点を通る円が描けるかを判定する問題です。
- 、、、テストケースの の総和と の総和はそれぞれ 以下
正確な問題文は元の問題ページを見てください。
base point を固定して円で分類する
Section titled “base point を固定して円で分類する”base point を とします。 は削除されないので常に集合にあり、すべての点を通る円があるなら、それは を通る円です。
base point 以外の点 について、
- が直線 上にあるなら、異なる 3 点が一直線上に並ぶので円は描けません
- そうでなければ、 を通る円がただ 1 つ決まります
したがって、答えが YES になるのは「直線 上の点がなく、base point 以外のすべての点について を通る円が同じ」ときです。点を「 を通る円」で分類して、種類が 1 種類以下かを見ればよいことになります。
円を誤差なく区別する
Section titled “円を誤差なく区別する”円の中心の座標で分類すると浮動小数点数の誤差が気になるので、整数だけで計算できる量を使います。
を原点に平行移動して とすると、原点と を通る円はすべて、あるパラメータ を使って
と書けます( は内積、 は外積 )。
この形に書ける理由
平面上の円は、 を定数ベクトル、 を定数として
と書けます(中心 、半径の 2 乗 )。
- 原点を通るので、 を代入して
- を通るので、 を代入して
後者について、 とおくと
となるので、 は に直交するベクトルです。 を 90° 回したベクトルを とすると、 に直交するベクトルは の実数倍なので、 () と書けます。よって
です。これを代入し、 を使うと
になります。
どの でも なので半径の 2 乗 は正で、本物の円になります。また、円が決まれば係数 が決まり、 から が決まります。つまり、 を通る円と実数 は 1 対 1 に対応します。
を代入して について解くと
です。円と は 1 対 1 に対応するので、2 点について とそれぞれを通る円が同じであることと、それぞれから求めた が等しいことは同値です。分母が になるのは が直線 上にあるときです。
は分子・分母とも整数なので、gcd で約分して分母を正にそろえた (分子, 分母) の組を辞書のキーにすれば、誤差なく分類できます。
クエリの処理
Section titled “クエリの処理”base point 以外の点のキーの個数を Counter で持ち、追加・削除のたびに増減します。直線 上の点はキーを None にしておけば、
Noneがない- キーの種類が 1 種類以下
のとき YES です。各点のキーの計算は gcd 1 回なので、座標の範囲を として全体で です。
公式解説の方針
Section titled “公式解説の方針”公式解説も、base point を固定して各点 について を通る円を考える点は同じです。直線 上にある点の個数と、 の外接円の中心(外心)の集合を管理し、直線上の点がなく外心がすべて一致するときに YES としています。外心は 2 本の垂直二等分線の交点として計算しています。
Python(upsolve)
from math import gcdfrom 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")