1. 從如何求點(diǎn)在四邊形中開始。

設(shè)有一四邊形為ABCD，一點(diǎn)P，求四邊形和P的位置關(guān)系。很明顯可以推廣到多邊形。。。

網(wǎng)上一般的算法是根據(jù)叉乘來做的，感覺叉乘太好用了qwq

首先定義四個(gè)向量

可以這么理解，如果是兩個(gè)向量頭和頭相連，如果角度>180°的話，那么這兩個(gè)向量的叉乘是一個(gè)小于0的數(shù)字。

如果像這樣的情況的話，旋轉(zhuǎn)一圈，B和C的夾角都大于180°了，那么這個(gè)P點(diǎn)肯定在這個(gè)多邊形的外邊。

點(diǎn)在多邊形外的情況

點(diǎn)在多邊形內(nèi)的情況

如果一開始的方向就是相反的話，那就整個(gè)符號(hào)都是相反的。需要保證四個(gè)向量的叉乘是同號(hào)的（一定要保證每個(gè)都同號(hào)）。

但是如果不是凸多邊形，或者這個(gè)順序是瞎給的怎么辦呢？那么我們就改題目吧……找這個(gè)凸包怎么找？

算法是這樣的：先找到一個(gè)頂點(diǎn)，比如最下的頂點(diǎn)。然后以這個(gè)頂點(diǎn)為基準(zhǔn)，求到其他點(diǎn)的向量。

構(gòu)造一個(gè)棧，把每個(gè)點(diǎn)按照y坐標(biāo)的順序排序，把前兩個(gè)點(diǎn)放入棧中，計(jì)算棧頂兩個(gè)點(diǎn)與該點(diǎn)三點(diǎn)向量是否是逆時(shí)針轉(zhuǎn)動(dòng)（第一步肯定是的）。

比如第一步棧中就是P，A，B三個(gè)點(diǎn)。PA和PB肯定是逆時(shí)針小于180度的。棧中元素為P，A，B

然后第二步，比較A，B，C三個(gè)點(diǎn)，AB和BC就不是逆時(shí)針小于180度了，扔掉B這個(gè)點(diǎn)。C進(jìn)入棧，所以現(xiàn)在棧中元素為P，A，C

第三步。D入棧，比較A，C，D三個(gè)點(diǎn)，是逆時(shí)針小于180度，現(xiàn)在是棧中元素為P，A，C，D。

第四步，E入棧，比較C，D，E三個(gè)點(diǎn)，是逆時(shí)針小于180度，現(xiàn)在的棧中結(jié)果是P，A，C，D，E。

第五步，所有的點(diǎn)遍歷完畢，算法結(jié)束。

輸出：凸包為：P，A，C，D，E（當(dāng)然用棧逆序打印也可以）