求任意多邊形面積-有向面積
給定多邊形的頂點座標（有序），讓你來求這個多邊形的面積，你會怎麼做？ 我們知道，任意多邊形都可以分割為N個三角形，所以，如果以這為突破點，那麼我們第一步就是把給定的多邊形，分割為數個三角形，分別求面積，最後累加就可以了，把多邊形分割為三角形的方式多種多樣，在這裡，我們按照如下圖的方法分割： 圖1 S […]
計算幾何
1/5ページ
計算幾何小結 我對計算幾何的理解以及叉積和點積
關於計算幾何 ： 在我看來計算幾何不同於解析幾何，解析幾何注重用代數的方法解決幾何問題，太暴力將幾何中一些優美的位置關係都給忽略了，都是通過代數解決，不夠優美，而計算幾何更加註重點和點、線和線、點和線的關係，通過位置關係轉化成向量的一些運算，相比於解析幾何，不僅僅突出了幾何關係的優美，並且通過幾何關 […]
計算幾何基礎——【點積和叉積的用處】
計算幾何是演算法競賽的一大塊，而叉積是計算機和的基礎。 首先叉積是計算說向量之間的叉積，那麼我們可以這樣定義向量，以及向量的運算子過載。 struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y) {} }; typedef P […]
2015年第六屆藍橋杯本科B組C 省賽個人題解
結果填空題： 解題技巧：對於藍橋杯的結果填空題，不管用什麼方式求解，只要能求出正確的結果就好。所以，這類題大部分都可以用暴力解決，有些題甚至直接手算就可以了。參考下面真題給出的題解就能體會得到。 1、獎券數目 有些人很迷信數字，比如帶“4”的數字，認為和“死”諧音，就覺得不吉利。 雖然這些說法純屬無 […]
- 2018.07.28
- acm, ACM演算法(題解)：, c計算幾何, qsc計算幾何, zjoi計算幾何,
計算幾何 ( 求凸包，計算三角形面積 )——最大三角形 ( HDU 2202 )
題目連結： http://acm.hdu.edu.cn/showproblem.php?pid=2202 分析： 給出平面上的N個點，在其中找出三個點，使得其構成的三角形的面積最大。 題解： 先用找出凸包上的所有點，然後一次列舉遍歷即可。 1.求凸包： int cmp(point a, point […]
計算幾何之半平面交、多邊形的核
半平面指一個平面的一半。比如在二維空間中，一條直線可以把整個平面分為兩部分，左邊是一個半平面右邊是一個半平面。而半平面交就是一堆半平面的交集，可以想象成線性規劃方程組A0x B0y C0>=0,A1x B1y C1<=0……A_0x B_0y C_0>=0, […]
Problem A Forever 0.5（推理構造）
題目:http://acm.fzu.edu.cn/problem.php?pid=2140 題意： 題目大意：給出n，要求找出n個點，滿足: 1)任意兩點間的距離不超過1； 2）每個點與（0，0）點的距離不超過1； 3）有n對點之間的距離剛好為1； 4）n個點組成的多邊形面積大於0.5； 5）n個點 […]
- 2018.07.28
- 計算幾何,
杭電1086（計算幾何）解題報告
http://acm.hdu.edu.cn/showproblem.php?pid=1086 You can Solve a Geometry Problem too Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K […]
bzoj1039 [ZJOI2008]無序運動Movement AC自動機 計算幾何
對於平移，旋轉，放縮，由於任意相鄰兩線段呈夾角不變，長度比例不變。因此只需要判斷相鄰兩線段長度比例和夾角不變。 夾角可以用叉積和點積的比值以及符號確定。 注意必須保留兩個符號。 然後可以用AC自動機計算，每個點的答案是這個點fail樹子樹中的點被長串經過的次數和。 對於翻轉操作只需把長的串翻轉再做一 […]
哈理工OJ 1559 線段相交（計算幾何）
http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1559 線段相交 Time Limit: 1000 MS Memory Limit: 10240 K Total Submit: 211 […]