首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

BZOJ 2508 簡單題:動態維護直線集合的最小距離平方和

     編輯:關於C++

問題描述

平面上動態維護直線集合,支持三操作:加直線(兩點式)、刪直線、查詢到所有直線距離平方和最小的點坐標。直線以一般式 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)。

注意事項

  • 浮點精度用 `EPS=1e-7` 判零。
  • 刪除操作給出直線編號,需存儲歷史直線。
  • 輸出格式 `%.2lf %.2lf`,若無解輸出 `0.00 0.00`(題目保證有解)。

總結

將幾何問題轉化為二次函數極值,利用係數增量維護實現動態操作,是計算幾何與動態數據結構結合的典型例題。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved