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