計算幾何

1/5ページ

求任意多邊形面積-有向面積

給定多邊形的頂點座標(有序),讓你來求這個多邊形的面積,你會怎麼做? 我們知道,任意多邊形都可以分割為N個三角形,所以,如果以這為突破點,那麼我們第一步就是把給定的多邊形,分割為數個三角形,分別求面積,最後累加就可以了,把多邊形分割為三角形的方式多種多樣,在這裡,我們按照如下圖的方法分割: 圖1 S […]

計算幾何小結 我對計算幾何的理解以及叉積和點積

關於計算幾何 : 在我看來計算幾何不同於解析幾何,解析幾何注重用代數的方法解決幾何問題,太暴力將幾何中一些優美的位置關係都給忽略了,都是通過代數解決,不夠優美,而計算幾何更加註重點和點、線和線、點和線的關係,通過位置關係轉化成向量的一些運算,相比於解析幾何,不僅僅突出了幾何關係的優美,並且通過幾何關 […]

2015年第六屆藍橋杯本科B組C 省賽個人題解

結果填空題: 解題技巧:對於藍橋杯的結果填空題,不管用什麼方式求解,只要能求出正確的結果就好。所以,這類題大部分都可以用暴力解決,有些題甚至直接手算就可以了。參考下面真題給出的題解就能體會得到。 1、獎券數目 有些人很迷信數字,比如帶“4”的數字,認為和“死”諧音,就覺得不吉利。 雖然這些說法純屬無 […]

計算幾何 ( 求凸包,計算三角形面積 )——最大三角形 ( HDU 2202 )

題目連結: http://acm.hdu.edu.cn/showproblem.php?pid=2202 分析: 給出平面上的N個點,在其中找出三個點,使得其構成的三角形的面積最大。 題解: 先用找出凸包上的所有點,然後一次列舉遍歷即可。 1.求凸包: int cmp(point a, point […]

bzoj1039 [ZJOI2008]無序運動Movement AC自動機 計算幾何

對於平移,旋轉,放縮,由於任意相鄰兩線段呈夾角不變,長度比例不變。因此只需要判斷相鄰兩線段長度比例和夾角不變。 夾角可以用叉積和點積的比值以及符號確定。 注意必須保留兩個符號。 然後可以用AC自動機計算,每個點的答案是這個點fail樹子樹中的點被長串經過的次數和。 對於翻轉操作只需把長的串翻轉再做一 […]