13年多校總結

     因為太水了, 幾場下來我都主要是看幾何, 其他方面就不考率拿多校來練習了~

     直接進入主題吧~

      計算幾何提供的最基礎的計算算法部分, 可以把它想象成像某種工具物品一樣性質的東西, 了解以後用到就伸手就行了, 但是對于計算幾何也是最重要的一部分。

 小的什麼距離計算, 點積叉積, 混合積, 公面共線, 大點的什麼凸包,最近點對,最遠點對也逃離不出這個範疇。這個部分的信手拈來是做計算幾何基礎的基礎,

 記得前面幾場單純考察的就是這個部分, 求圓柱體最短空間距離~~  求線段和雨滴的交點~~, 求三角形面積并~~~（哭,tooSimply）。

 總之就一句話,這部分需要確定寫的穩,其次寫的快~

     據說因為各校神牛洶湧澎湃,後來題目加大難度了~。其實我想說的是, 别想着計算幾何就單純和幾何相關~。計算結合會通過結合一些其他算法來加深難度。

如果沒做過而且其他的相關算法太弱, 一句話題就可以足夠打發時間了,比如：”求平面内點集最多點凸包“, ”求平面内最大空凸包“,這些需要DP的思維來解題。

或者像後來多校的題結合了DP,數學歸納等, 需要證明,不然誰敢YY浪費時間。

     如果前面的條件都達到了,那我覺得出不了題也沒什麼遺憾的了,  剩下就是YY出題人的想法, 他怎麼寫的标程啊, 因為這個會影響到精度或者邊角問題等等~

    暫時計算幾何想法就這麼多吧~,

    因為前前面提到幾何結合了其他算法,那麼就再多說幾句吧~

    和計算幾何結合比較多的思想通常有： DP, 貪心, 搜尋, 數學歸納 , YY（歡迎補充~）

    因為這些思想泛用太強大了~, 具體問題要具體分析, 是以大部分水準隻能依靠經驗,總結來提升~。

   DP：看怎麼分解子問題, 如果子問題能正确轉移得出規模更大的問題, 就能寫~

   貪心： YY出局部問題操作方法, 使全局最優~, 有些難得證明隻能YY~

   搜尋：最多用到BFS,DFS(這兩個建立的搜尋樹可以通過排序,貪心什麼進行剪枝,總之不要覺得簡單),A*等等, 還可以建立圖的模型,用圖論來解(扯到蛋了)~

   數學歸納：寫出表達式,求最優或者,尋值~

   YY：聰明的你的靈光一閃~

  //小結end;