計算幾何是為Regional臨時抱佛腳搞的。。還很菜。。大牛們多指教。。
評述的話主要是自己以后找起題來方便。。大牛們忽略就好。。
1031 求多邊形累計偏轉(zhuǎn)角。。抄啊抄。。
1039 點積叉積應(yīng)用。。自己的死活過不了。。計算幾何啊。。。
1066 方法是枚舉目標(biāo)點到邊上每兩點中點構(gòu)成的線段，找與其他線段相交數(shù)最少的
1106 判斷半圓最多覆蓋多少點
1113 簡單凸包。。凸包周長加半徑L圓的周長。。
1127 并查集+線段相交
1151 坐標(biāo)離散化加掃描線，第一次了解。。
1228 凸包唯一確定問題。。Discuss什么都說了。。
1244 不要想復(fù)雜。。O(n^3)+正常建坐標(biāo)系就過了。。
1265 求頂點為整數(shù)的任意多邊形內(nèi)部整點數(shù)(Pick定理)，邊上整點數(shù)(GCD)，面積(叉積)
1266 求能覆蓋一條弧的最小矩形面積，矩形頂點是整點
1279 直接貼的半平面交模板。。
1319 應(yīng)該算是簡單幾何。。注意邊長小于1 的情況
1329 浙大模版真好用。。，但是這題輸出被我改得好惡心
1380 計算幾何，判斷小矩形能否放進(jìn)大矩形。。可旋轉(zhuǎn)。。
1389 類似1151
1410 判斷矩形與一線段是否相交，注意線段在矩形內(nèi)部的情況
1473 求首尾兩點距離。。比較水
1474 半平面交求核面積抄模板死活過不了。。無奈抄了神奇的標(biāo)程。。
1584 判凸邊形，計算點到凸包邊上最小距離，判點在凸包內(nèi)
1654 求多邊形面積。。抄公式。。
1696 叉積判斷是順時針還是逆時針方向，點積
1673 直接抄的浙大模版。。一次AC。。好爽。。。
1859 分奇偶按左右分別不同方向排序，看能否配對
1927 不難，因為沒考慮只能圍成一個小圓的情況WA無數(shù)次。。
1940 很久以前做完1939就看了這個，，沒注意頂點是奇數(shù)的條件。。死活想不出。。。
1971 找每兩個點的中點，排序。。數(shù)構(gòu)成的平行四邊形數(shù)
1981 求落在單位圓里的點數(shù)。。枚舉。。
2002 給若干點，求構(gòu)成多少正方形。。枚舉兩點二分查找是否有符合條件的另兩點
2007 不懂自己按tan排序為什么錯。。實在受不了。。抄了網(wǎng)上一個不太懂的算法。。
2079 用原始的凸包模板TLE無數(shù)次，再優(yōu)化只能到WA。。ft。。。傳說中的旋轉(zhuǎn)卡殼好強大。。勉強理解了。。自己還寫不出
2187 凸包。。抄浙大模板。。
2208 已知六邊求三棱錐體積。。抄公式。。。
2354 算地球上兩點距離。。經(jīng)緯度形式給出。。地理沒學(xué)好。。抄了部分代碼。。
2318 叉積判斷同側(cè)。。二分確定區(qū)間
2398 同2318，做一送一
2546 求兩圓相交的面積，用到海倫公式
2653 鏈表+線段相交。。。第一次完全自己寫鏈表。。搞得想吐血
2780 類似3512
2954 類似1265 ，求三角形內(nèi)部整點數(shù)，Pick定理
2957 以為是簡單的幾何題，這題做的人好少。。沒想到還要用坐標(biāo)旋轉(zhuǎn)什么的。。第一次做計算幾何
3130 半平面交求多邊形核的存在性。。ZZY大牛的論文看過。。寫不出來。。模板不太懂。。超長的模板。。7174B。。。
3304 判斷直線和線段相交
3335 跟3130不同的另一個半平面交模板。。
3348 求凸包面積。。函數(shù)全部來自浙大模板。?？磥碚愦竽０搴軓姾?。。沒Discuss種種錯誤
3407 類似2354，已知兩點經(jīng)緯求距離
3432 同2002
3512 枚舉斜率+sort。。。抄的別人的思路。。類似1118.。但是O(n^3)必掛。。。
3565 貌似是匹配的問題。。上網(wǎng)搜了個用計算幾何調(diào)整法過的。。過程類似交換排序
3608 求凸包間最小距離，旋轉(zhuǎn)卡殼。。很強大
3714 最近點對問題，王曉東的書沒看懂。。