為什麽 學好幾何對計算機競賽 至關重要？

很驚訝看到這裏幾乎所有人都認為幾何對計算機競賽 沒有用。

如果不想贏，確實幾何不重要。否則 至關重要。

如果 熟悉 ICPC競賽的，最後一定乾坤的題，幾乎都是幾何題。

最常見的幾何題有 Delaunay triangulation, Sweep line, Convex hulls 等等，不僅要掌握 好平麵幾何，特別是立體幾何，還有計算幾何。對計算三維立體的 距離，角度，麵積，體積 的算法滾瓜爛熟，三維矢量計算滾瓜爛熟，如何計算Voronoi diagram，各種最短路徑等等

為什麽競賽中的幾何題最難，也最能讓你脫穎而出。

• 因為首先大家普遍幾何不好，
• 第二，幾何複雜，特別是三維數據龐大，
• 第三，立體幾何 需要非常好的空間想象力，能 visualize,
• 第四，幾何的模型計算往往是非線性的，
• 第五，曲線，曲麵更難，你可以根據pixel數目計算體積，但如何計算曲線長度，並非易事
• 第六，幾何數值不像數論那樣簡單的整數，幾何數值都是 double float, 而且精度非常重要，加上 四舍五入的誤差，往往會造成 不穩定性。還常見 overflow / underflow 問題
• 第七，非常測試，幾何問題的test case 很難考慮周全。

暫時就列這麽多了，練好幾何，是計算機競賽取勝的關鍵