計(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)大矩形。?？尚D(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è)较?，點(diǎn)積

1673   直接抄的浙大模版。。一次AC。。好爽。。。

1859   分奇偶按左右分別不同方向排序，看能否配對(duì)

1927   不難，因?yàn)闆](méi)考慮只能圍成一個(gè)小圓的情況WA無(wú)數(shù)次。。

1940   很久以前做完1939就看了這個(gè)，，沒(méi)注意頂點(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)緯度形式給出。。地理沒(méi)學(xué)好。。抄了部分代碼。。

2318   叉積判斷同側(cè)。。二分確定區(qū)間

2398   同2318，做一送一

2546   求兩圓相交的面積，用到海倫公式

2653   鏈表+線段相交。。。第一次完全自己寫鏈表。。搞得想吐血

2780   類似3512

2954   類似1265 ，求三角形內(nèi)部整點(diǎn)數(shù)，Pick定理

2957   以為是簡(jiǎn)單的幾何題，這題做的人好少。。沒(méi)想到還要用坐標(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)悍。。沒(méi)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)題，王曉東的書(shū)沒(méi)看懂。。