平面上動態維護直線集合,支持三操作:加直線(兩點式)、刪直線、查詢到所有直線距離平方和最小的點坐標。直線以一般式 Ax+By+C=0 存儲,歸一化後距離平方為 (Ax+By+C)²/(A²+B²)。
目標函數 Σ (Aᵢx+Bᵢy+Cᵢ)²/(Aᵢ²+Bᵢ²) 展開為二元二次函數:
f(x,y) = a x² + b y² + c + d xy + e x + f y
其中係數可增量維護:加直線時累加對應項,刪直線時減去。
對 x,y 求偏導為 0 得線性方程組:
2a x + d y + e = 0 d x + 2b y + f = 0
解得極值點 (x₀,y₀)。特殊情況:若 Hessian 矩陣奇異(d²=4ab),退化為一維或常數,需分情況處理(代碼中有詳細分支)。
用結構體存儲每條直線歸一化係數,加/刪時更新 6 個全域係數 a,b,c,d,e,f,均為 O(1)。查詢時解方程 O(1)。總複雜度 O(n)。
將幾何問題轉化為二次函數極值,利用係數增量維護實現動態操作,是計算幾何與動態數據結構結合的典型例題。