算幾何入門：向量叉積與二分查找在POJ 2318 TOYS問題中的應(yīng)用)
1. 項(xiàng)目概述從一道經(jīng)典幾何題看計(jì)算幾何的實(shí)戰(zhàn)思維看到POJ - 2318 -- TOYS這個(gè)標(biāo)題很多刷過POJ北京大學(xué)在線評測系統(tǒng)題目的朋友可能會心一笑這是一道非常經(jīng)典的計(jì)算幾何入門題。它不像那些復(fù)雜的算法題讓人望而生畏而是用一個(gè)非常生活化的場景——判斷一堆玩具娃娃掉進(jìn)了哪個(gè)盒子分區(qū)——來考察一個(gè)核心的幾何工具向量的叉積。這道題之所以經(jīng)典是因?yàn)樗昝赖卦忈屃巳绾螌⒊橄蟮臄?shù)學(xué)工具應(yīng)用于具體的“定位”問題并且提供了從最直觀的暴力解法到需要稍加思考的二分優(yōu)化解法形成了一個(gè)清晰的思維進(jìn)階路徑。對于正在學(xué)習(xí)計(jì)算幾何或者想要鞏固基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法結(jié)合應(yīng)用的朋友來說這道題是一個(gè)絕佳的練手材料。它不要求你掌握特別高深的知識但能讓你深刻理解叉積的符號意義并體會不同算法策略帶來的效率差異。接下來我就結(jié)合自己多次解題和教學(xué)的經(jīng)驗(yàn)把這背后的門道掰開揉碎了講清楚。2. 問題核心與幾何建模解析2.1 問題場景還原與抽象題目的描述非常形象有一個(gè)大長方形箱子從左到右被若干塊豎直的隔板分割成了若干個(gè)區(qū)域。這些隔板的上端和下端分別頂在箱子的上邊界和下邊界上但它們的橫坐標(biāo)是依次遞增的。然后我們會隨機(jī)往箱子里扔一些玩具抽象為平面上的點(diǎn)。我們的任務(wù)就是對于每一個(gè)玩具點(diǎn)判斷它落在了哪個(gè)隔板區(qū)間內(nèi)。這聽起來就像是一個(gè)兒童游樂場的收納問題但在計(jì)算機(jī)看來我們需要建立一個(gè)精確的數(shù)學(xué)模型。首先我們將整個(gè)場景放置在一個(gè)二維笛卡爾坐標(biāo)系中。通常我們會將箱子的左下角設(shè)為原點(diǎn)(0, 0)右上角設(shè)為(X, Y)。那么n塊隔板就對應(yīng)著n條線段。每條線段連接兩個(gè)點(diǎn)上端點(diǎn)(Ui, Y)和下端點(diǎn)(Li, 0)并且滿足Li和Ui都是嚴(yán)格遞增的即隔板不會交叉從左到右排列。這樣n塊隔板就將箱子分割成了n1個(gè)區(qū)域從左到右編號為0到n。給定m個(gè)玩具點(diǎn)的坐標(biāo)(x, y)我們需要輸出每個(gè)區(qū)域最終落入了多少個(gè)玩具。注意輸入數(shù)據(jù)通常保證玩具點(diǎn)不會恰好落在隔板線段上也不會落在箱子邊界之外。這是一個(gè)非常重要的簡化條件避免了處理邊界情況的麻煩讓我們可以專注于核心算法邏輯。2.2 核心工具向量叉積的符號意義解決這個(gè)問題的鑰匙就是向量的叉積。對于二維向量a (x1, y1)和b (x2, y2)它們的叉積在二維中常指標(biāo)量叉積或外積定義為a × b x1*y2 - y1*x2。這個(gè)數(shù)值的幾何意義非常強(qiáng)大絕對值表示以a和b為鄰邊構(gòu)成的平行四邊形的有向面積。符號這是我們本題最關(guān)心的。它表示向量b相對于向量a的旋轉(zhuǎn)方向。如果a × b 0說明b在a的逆時(shí)針方向左手系則為順時(shí)針。如果a × b 0說明b在a的順時(shí)針方向。如果a × b 0說明a和b共線方向相同或相反。如何應(yīng)用到我們的問題呢對于任意一個(gè)玩具點(diǎn)P(x, y)和一塊隔板線段ABA為上端點(diǎn)B為下端點(diǎn)我們可以構(gòu)造兩個(gè)向量向量AB從隔板上端點(diǎn)指向下端點(diǎn)即(L - U, 0 - Y) (L-U, -Y)。向量AP從隔板上端點(diǎn)指向玩具點(diǎn)即(x - U, y - Y)。計(jì)算叉積CP AB × AP。其符號的幾何意義可以理解為點(diǎn)P相對于有向線段AB的位置。如果CP 0點(diǎn)P在AB的左側(cè)以A為起點(diǎn)B為終點(diǎn)看。如果CP 0點(diǎn)P在AB的右側(cè)。為什么你可以把AB想象成面前的一條垂直參考線。AB × AP 0意味著AP向量相對于AB向量是逆時(shí)針旋轉(zhuǎn)的對于豎直向下的AB來說AP要逆時(shí)針轉(zhuǎn)那P點(diǎn)自然就在AB的左邊了。反之亦然。這個(gè)判斷是整個(gè)問題求解的基石。對于一塊隔板我們知道它左邊的區(qū)域編號是i-1右邊是i。如果我們能判斷點(diǎn)P在某塊隔板的右邊那就說明它至少不在編號小于i的區(qū)域里它可能位于i,i1, ... 這些區(qū)域。我們的任務(wù)就是為每個(gè)點(diǎn)找到最左邊的那塊隔板使得點(diǎn)P位于它的右側(cè)那么這個(gè)點(diǎn)就屬于這塊隔板右邊的那個(gè)區(qū)域。3. 解法一暴力遍歷法——最直觀的入門實(shí)現(xiàn)3.1 算法思路與實(shí)現(xiàn)步驟暴力法的思想直接源于上述幾何判斷對于每一個(gè)玩具點(diǎn)我們從左到右從第1塊到第n塊隔板依次檢查。對于第i塊隔板計(jì)算點(diǎn)P相對于它的位置。如果點(diǎn)P在第i塊隔板的左側(cè)CP 0說明點(diǎn)P還沒有越過這塊隔板它應(yīng)該位于第i-1個(gè)區(qū)域。此時(shí)我們可以停止遍歷記錄結(jié)果。如果點(diǎn)P在第i塊隔板的右側(cè)CP 0說明點(diǎn)P已經(jīng)在這塊隔板的右邊了我們繼續(xù)檢查下一塊隔板。如果我們檢查完了所有n塊隔板點(diǎn)P都在它們的右側(cè)那么這個(gè)點(diǎn)就落在了最右邊的第n個(gè)區(qū)域。實(shí)操步驟數(shù)據(jù)讀取與存儲讀入箱子右上角坐標(biāo)X, Y隔板數(shù)量n玩具數(shù)量m。然后讀入n塊隔板的上下端點(diǎn)橫坐標(biāo)Ui和Li通常存儲為兩個(gè)數(shù)組up[n]和low[n]。接著讀入m個(gè)玩具點(diǎn)的坐標(biāo)(x, y)。初始化計(jì)數(shù)數(shù)組創(chuàng)建一個(gè)大小為n1的數(shù)組cnt初始化為0用于記錄每個(gè)區(qū)域的玩具數(shù)量。遍歷每個(gè)玩具點(diǎn)對第j個(gè)玩具點(diǎn)(x, y) a. 設(shè)置一個(gè)變量region 0這是默認(rèn)區(qū)域最左邊如果點(diǎn)在所有隔板右側(cè)則最終區(qū)域就是n。 b. 循環(huán)i從0到n-1對應(yīng)第1到第n塊隔板 i. 計(jì)算向量AB (low[i] - up[i], -Y)。 ii. 計(jì)算向量AP (x - up[i], y - Y)。 iii. 計(jì)算叉積cross AB.x * AP.y - AB.y * AP.x。 iv. 如果cross 0說明點(diǎn)在當(dāng)前隔板左側(cè)跳出循環(huán)此時(shí)region的值i就是目標(biāo)區(qū)域編號。 v. 如果cross 0說明點(diǎn)在當(dāng)前隔板右側(cè)region自增1繼續(xù)檢查下一塊隔板。 c. 循環(huán)結(jié)束后region的值即為該玩具點(diǎn)所在區(qū)域編號0 到 n。執(zhí)行cnt[region]。輸出結(jié)果按照格式輸出cnt[0]到cnt[n]的值。3.2 代碼實(shí)現(xiàn)片段與關(guān)鍵點(diǎn)#include iostream #include cstring using namespace std; struct Point { int x, y; Point(int _x0, int _y0): x(_x), y(_y) {} }; // 計(jì)算叉積 (b-a) × (c-a) int cross(const Point a, const Point b, const Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } int main() { int n, m; int X1, Y1, X2, Y2; // 箱子左上角和右下角但通常我們只需要Y1上, Y2下 int U[5005], L[5005]; // 假設(shè)n最大5000 Point toys[5005]; int cnt[5005] {0}; while (cin n n) { cin m X1 Y1 X2 Y2; for (int i 0; i n; i) { cin U[i] L[i]; // 上端點(diǎn)和下端點(diǎn)x坐標(biāo) } for (int i 0; i m; i) { cin toys[i].x toys[i].y; } // 處理每個(gè)玩具 for (int i 0; i m; i) { Point p toys[i]; int region 0; // 遍歷每一塊隔板 for (int j 0; j n; j) { Point a(U[j], Y1); // 隔板上端點(diǎn) Point b(L[j], Y2); // 隔板下端點(diǎn) // 計(jì)算叉積判斷點(diǎn)p在向量ab的左側(cè)還是右側(cè) // 注意這里用a, b, p的順序計(jì)算的是 (b-a)×(p-a) // 如果結(jié)果 0則p在ab左側(cè)屬于當(dāng)前region if (cross(a, b, p) 0) { break; // 找到所屬區(qū)域跳出循環(huán) } else { region; // 點(diǎn)在右側(cè)區(qū)域編號1 } } cnt[region]; } // 輸出結(jié)果 for (int i 0; i n; i) { cout i : cnt[i] endl; } cout endl; memset(cnt, 0, sizeof(cnt)); // 多組數(shù)據(jù)清空計(jì)數(shù)器 } return 0; }關(guān)鍵點(diǎn)與注意事項(xiàng)叉積函數(shù)的設(shè)計(jì)我習(xí)慣實(shí)現(xiàn)一個(gè)計(jì)算(b-a)×(c-a)的函數(shù)這樣參數(shù)意義明確點(diǎn)a是向量起點(diǎn)b是第一個(gè)向量終點(diǎn)c是第二個(gè)向量終點(diǎn)。在本題中a是隔板上端點(diǎn)b是隔板下端點(diǎn)c是玩具點(diǎn)。判斷cross(a, b, p) 0即點(diǎn)p在向量ab左側(cè)。坐標(biāo)與方向務(wù)必注意題目給出的Y1和Y2哪個(gè)是上邊界哪個(gè)是下邊界。通常Y1 Y2因?yàn)閅坐標(biāo)向下增長。這會影響向量AB的y分量計(jì)算。在上面的代碼中a(U[j], Y1),b(L[j], Y2)所以AB (L[j]-U[j], Y2-Y1)由于Y2-Y1為負(fù)向量是向下的這與我們“從上到下”的隔板方向一致。循環(huán)終止條件暴力法的內(nèi)層循環(huán)可能提前跳出當(dāng)找到區(qū)域時(shí)平均來看效率尚可但在最壞情況下所有點(diǎn)都在最右邊區(qū)域每個(gè)點(diǎn)都要遍歷所有n塊隔板。4. 解法二二分查找法——效率的優(yōu)化4.1 優(yōu)化動機(jī)與可行性分析暴力法的時(shí)間復(fù)雜度是O(m * n)在n和m都達(dá)到5000量級時(shí)計(jì)算量是2500萬在POJ的舊評測機(jī)上可能處于超時(shí)的邊緣或者需要優(yōu)化常數(shù)。我們注意到一個(gè)關(guān)鍵性質(zhì)隔板的橫坐標(biāo)是嚴(yán)格遞增的。這意味著對于一個(gè)給定的玩具點(diǎn)P它相對于這些隔板的位置關(guān)系是“單調(diào)”的。想象一下從左到右掃描隔板點(diǎn)P開始時(shí)可能在某塊隔板左側(cè)CP 0隨著隔板越來越靠右點(diǎn)P終將變?yōu)樵谄溆覀?cè)CP 0。并且這個(gè)變化是一次性的不會出現(xiàn)左右搖擺的情況因?yàn)楦舭迨侵本€且點(diǎn)不在隔板上。更準(zhǔn)確地說函數(shù)f(i) sign( cross( a_i, b_i, P ) )是一個(gè)關(guān)于隔板索引i的單調(diào)非遞減函數(shù)值從1或0變?yōu)?1。這完美符合二分查找的應(yīng)用條件在一個(gè)有序序列中尋找一個(gè)邊界使得邊界左側(cè)滿足某個(gè)條件點(diǎn)P在隔板右側(cè)邊界右側(cè)不滿足該條件點(diǎn)P在隔板左側(cè)。我們要找的就是最左邊的那個(gè)使得點(diǎn)P在其左側(cè)的隔板這個(gè)隔板的索引i就對應(yīng)點(diǎn)P的區(qū)域編號i如果從0開始計(jì)數(shù)隔板。如果所有隔板都滿足點(diǎn)在其右側(cè)則區(qū)域編號為n。4.2 二分查找的實(shí)現(xiàn)細(xì)節(jié)二分查找的區(qū)間通常設(shè)為[0, n]其中n是隔板數(shù)量。我們需要定義判斷條件。設(shè)當(dāng)前檢查的隔板索引為mid。如果點(diǎn)P在第mid塊隔板的右側(cè)cross(a_mid, b_mid, P) 0說明目標(biāo)隔板點(diǎn)P左側(cè)的隔板還在更右邊我們應(yīng)該搜索右半?yún)^(qū)間[mid1, high]。如果點(diǎn)P在第mid塊隔板的左側(cè)cross(a_mid, b_mid, P) 0說明當(dāng)前隔板可能就是目標(biāo)或者目標(biāo)在左邊我們應(yīng)該搜索左半?yún)^(qū)間[low, mid]。注意這里不能是mid-1因?yàn)閙id本身可能是答案。我們最終要找到的是第一個(gè)使得點(diǎn)P在其左側(cè)的隔板索引。標(biāo)準(zhǔn)的二分查找模板尋找左邊界如下int binarySearch(const Point p, int n, int U[], int L[], int Y1, int Y2) { int low 0, high n; // 注意 high 初始為 n表示可能的結(jié)果范圍是 [0, n] while (low high) { int mid low (high - low) / 2; Point a(U[mid], Y1); Point b(L[mid], Y2); if (cross(a, b, p) 0) { // 點(diǎn)p在隔板mid右側(cè)目標(biāo)區(qū)域在右邊 low mid 1; } else { // 點(diǎn)p在隔板mid左側(cè)或共線題目保證不共線目標(biāo)區(qū)域可能是mid或左邊 high mid; } } // 循環(huán)結(jié)束時(shí)low high即為所求的區(qū)域編號 // 解釋low 是第一個(gè)滿足 cross 0 的隔板索引即點(diǎn)p在其左側(cè)的隔板。 // 這個(gè)索引值正好就是區(qū)域編號。例如第一個(gè)左側(cè)隔板是i則點(diǎn)落在i號區(qū)域。 return low; }對返回值low的理解二分查找結(jié)束后low的值表示點(diǎn)P在low號隔板的左側(cè)而在low-1號隔板的右側(cè)。因此點(diǎn)P就落在了low號區(qū)域。特別地如果low n說明點(diǎn)P在所有n塊隔板的右側(cè)因此落在第n號區(qū)域。這與暴力法的邏輯完全一致。4.3 復(fù)雜度對比與適用場景暴力法時(shí)間復(fù)雜度O(m * n)空間復(fù)雜度O(n m)。代碼極其簡單不易出錯(cuò)非常適合在時(shí)間限制寬松、或者n, m較小時(shí)例如均小于1000作為首選。在面試或快速原型驗(yàn)證時(shí)先寫出暴力法確保邏輯正確也是一個(gè)好習(xí)慣。二分法時(shí)間復(fù)雜度O(m * log n)空間復(fù)雜度O(n m)。在n較大時(shí)如5000log2(5000) ≈ 13效率提升非常顯著m*n的2500萬次計(jì)算降至m*log n的約65000次計(jì)算完全避免了超時(shí)風(fēng)險(xiǎn)。如何選擇追求效率與通用性毫無疑問選擇二分法。這是計(jì)算幾何中利用單調(diào)性進(jìn)行優(yōu)化的典型范例掌握它對于解決更復(fù)雜的問題如點(diǎn)在多邊形內(nèi)的判斷、凸包等有啟發(fā)意義。初學(xué)與調(diào)試可以先實(shí)現(xiàn)暴力法用其生成的數(shù)據(jù)對二分法進(jìn)行對拍測試確保二分查找的邊界條件完全正確。注意點(diǎn)二分法的實(shí)現(xiàn)需要格外小心邊界條件。上面的模板中初始high n以及循環(huán)條件while (low high)和high mid的賦值是處理“尋找左邊界”問題的常見寫法需要理解其含義死記硬背容易出錯(cuò)。5. 實(shí)戰(zhàn)中的常見問題與深度排查即便理解了算法在實(shí)現(xiàn)時(shí)還是會遇到一些“坑”。下面是我在多次解題和教學(xué)中總結(jié)出來的常見問題。5.1 叉積計(jì)算與方向判斷錯(cuò)誤這是最常見的問題。核心在于向量構(gòu)造的順序和叉積公式的應(yīng)用。問題表現(xiàn)所有點(diǎn)都被判到同一個(gè)區(qū)域如最左邊或最右邊或者結(jié)果看起來隨機(jī)混亂。排查步驟確認(rèn)向量起點(diǎn)確保你計(jì)算的叉積是(隔板向量) × (點(diǎn)到起點(diǎn)的向量)。常見的函數(shù)是cross(a, b, p)計(jì)算(b-a)×(p-a)。這里的a必須是隔板的上端點(diǎn)。確認(rèn)坐標(biāo)對應(yīng)檢查你傳入的Y1和Y2是否與點(diǎn)的y坐標(biāo)在同一個(gè)坐標(biāo)系下。比如題目輸入可能是Y1為上Y2為下那么a.y Y1,b.y Y2。如果搞反了向量的方向就反了叉積符號也就反了。手工驗(yàn)證找一個(gè)簡單例子比如只有一塊隔板在x5的位置箱子上下邊界為0和10。分別取點(diǎn)(2, 5)應(yīng)在左側(cè)和(8, 5)應(yīng)在右側(cè)手工計(jì)算叉積看符號是否符合你的判斷邏輯0左還是0左。我的心得統(tǒng)一使用一個(gè)經(jīng)過測試的cross函數(shù)并明確其幾何意義cross(a,b,c)0表示c在ab左側(cè)。在題目中固定使用一種判斷標(biāo)準(zhǔn)不要混用。5.2 二分查找的邊界條件陷阱二分查找的細(xì)節(jié)決定成敗。問題表現(xiàn)部分點(diǎn)區(qū)域判斷錯(cuò)誤尤其是在邊緣區(qū)域0區(qū)或n區(qū)。排查步驟初始區(qū)間為什么high初始是n而不是n-1因?yàn)榇鸢缚赡苁莕點(diǎn)在所有隔板右側(cè)。搜索區(qū)間[0, n]是左閉右開[low, high)的表示high初始值n表示有效的索引范圍是0到n-1但n本身作為一個(gè)可能的答案表示“第n個(gè)區(qū)域”需要被包含在搜索空間中。在循環(huán)中我們通過mid訪問隔板數(shù)組時(shí)mid的范圍是[0, n-1]當(dāng)low被推到n時(shí)循環(huán)結(jié)束n就是答案。循環(huán)條件與更新while (low high)確保退出時(shí)low high。當(dāng)cross 0點(diǎn)在右側(cè)時(shí)答案一定在mid右邊所以low mid 1。當(dāng)cross 0點(diǎn)在左側(cè)時(shí)mid可能是答案所以high mid保留mid在區(qū)間內(nèi)。測試用例構(gòu)造極端數(shù)據(jù)測試。例如沒有隔板n0點(diǎn)應(yīng)該全部落在區(qū)域0。只有一塊隔板點(diǎn)分別在左右側(cè)。所有點(diǎn)都在最左或最右區(qū)域。我的心得理解二分查找的“區(qū)間不變式”。在上述寫法中循環(huán)不變式是答案區(qū)域編號一定在區(qū)間[low, high)內(nèi)。初始化時(shí)區(qū)間是[0, n)包含了所有可能答案。每次循環(huán)根據(jù)mid處的判斷我們將答案不可能存在的半邊區(qū)間排除并保持答案仍在新的[low, high)區(qū)間內(nèi)。當(dāng)區(qū)間縮小到只有一個(gè)元素 (low high) 時(shí)那個(gè)位置就是答案。5.3 多組數(shù)據(jù)輸入的初始化問題POJ的題目經(jīng)常有多組測試數(shù)據(jù)直到輸入n0為止。問題表現(xiàn)第二組數(shù)據(jù)的結(jié)果被第一組數(shù)據(jù)污染輸出錯(cuò)誤。解決方案在每處理完一組數(shù)據(jù)后必須清空用于計(jì)數(shù)的數(shù)組cnt。使用memset(cnt, 0, sizeof(cnt))或循環(huán)歸零。注意如果使用C的vector需要在讀取新的n后resize(n1)并賦零。額外提醒注意題目輸出的格式每組數(shù)據(jù)結(jié)果后面有時(shí)需要跟一個(gè)空行。仔細(xì)閱讀輸出說明。6. 從TOYS問題延伸的思考與技巧解決POJ 2318不僅僅是為了AC一道題更是為了掌握一類思想。6.1 叉積判斷點(diǎn)與線關(guān)系的通用性本題利用叉積判斷點(diǎn)在有向線段的左右側(cè)這是計(jì)算幾何中最基礎(chǔ)、最常用的操作之一。這個(gè)技巧可以推廣到許多問題線段相交判斷快速排斥實(shí)驗(yàn)后利用叉積檢查兩點(diǎn)是否在線段兩側(cè)。凸多邊形包含點(diǎn)判斷依次判斷點(diǎn)是否在多邊形每條邊的同一側(cè)例如左側(cè)如果是則在多邊形內(nèi)。極角排序以某個(gè)點(diǎn)為基點(diǎn)計(jì)算其他點(diǎn)相對于該點(diǎn)的向量的叉積用于排序。理解其本質(zhì)叉積的符號反映了兩個(gè)向量的“旋轉(zhuǎn)方向”從而可以建立“方向”和“位置”的聯(lián)系。6.2 二分查找的單調(diào)性來源本題二分可行的根本原因是隔板的有序性Ui和Li遞增導(dǎo)致了位置判斷函數(shù)的單調(diào)性。在實(shí)際問題中如何發(fā)現(xiàn)并利用這種單調(diào)性是一種重要的解題能力。例如在一些最優(yōu)化問題中如果決策函數(shù)是單調(diào)的就可以用二分法來枚舉答案將最優(yōu)化問題轉(zhuǎn)化為判定問題。6.3 浮點(diǎn)數(shù)處理的注意事項(xiàng)本題輸入坐標(biāo)是整數(shù)所以用整數(shù)計(jì)算叉積完全沒問題避免了浮點(diǎn)數(shù)精度誤差。但如果坐標(biāo)是浮點(diǎn)數(shù)在判斷cross 0或cross 0時(shí)就不能直接與0比較而應(yīng)該與一個(gè)極小的精度容忍值eps如1e-10比較。例如if (cross eps)判斷為正if (cross -eps)判斷為負(fù)否則認(rèn)為共線。在POJ 2318中明確點(diǎn)不在隔板上整數(shù)計(jì)算足夠安全但養(yǎng)成這個(gè)意識對處理其他計(jì)算幾何題目至關(guān)重要。6.4 調(diào)試與對拍策略對于這類問題高效的調(diào)試策略能節(jié)省大量時(shí)間。小數(shù)據(jù)手工模擬畫出坐標(biāo)系標(biāo)出隔板和幾個(gè)測試點(diǎn)手工計(jì)算叉積和區(qū)域與程序輸出對比。暴力法對拍這是最有效的方法。先寫一個(gè)絕對正確的暴力解法O(n*m)再寫優(yōu)化算法二分法。用隨機(jī)生成的大量數(shù)據(jù)注意保證點(diǎn)不在隔板上同時(shí)運(yùn)行兩個(gè)程序?qū)Ρ容敵?。POJ的n, m最多5000在本地生成數(shù)據(jù)對拍很容易。邊界測試專門生成n0,n1,m0如果允許以及點(diǎn)緊貼隔板但不相交的數(shù)據(jù)進(jìn)行測試。最后這道題看似簡單卻涵蓋了計(jì)算幾何的基石思想、基礎(chǔ)算法的優(yōu)化策略以及嚴(yán)謹(jǐn)?shù)拇a實(shí)現(xiàn)細(xì)節(jié)。我建議在理解的基礎(chǔ)上能夠不參考任何代碼獨(dú)立完成從暴力到二分的兩種實(shí)現(xiàn)并通過在線評測系統(tǒng)進(jìn)行提交驗(yàn)證。這個(gè)過程收獲的遠(yuǎn)不止一個(gè)“Accepted”。 計(jì)算幾何入門：向量叉積與二分查找在POJ 2318 TOYS問題中的應(yīng)用
1. 項(xiàng)目概述從一道經(jīng)典幾何題看計(jì)算幾何的實(shí)戰(zhàn)思維看到POJ - 2318 -- TOYS這個(gè)標(biāo)題很多刷過POJ北京大學(xué)在線評測系統(tǒng)題目的朋友可能會心一笑這是一道非常經(jīng)典的計(jì)算幾何入門題。它不像那些復(fù)雜的算法題讓人望而生畏而是用一個(gè)非常生活化的場景——判斷一堆玩具娃娃掉進(jìn)了哪個(gè)盒子分區(qū)——來考察一個(gè)核心的幾何工具向量的叉積。這道題之所以經(jīng)典是因?yàn)樗昝赖卦忈屃巳绾螌⒊橄蟮臄?shù)學(xué)工具應(yīng)用于具體的“定位”問題并且提供了從最直觀的暴力解法到需要稍加思考的二分優(yōu)化解法形成了一個(gè)清晰的思維進(jìn)階路徑。對于正在學(xué)習(xí)計(jì)算幾何或者想要鞏固基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)與算法結(jié)合應(yīng)用的朋友來說這道題是一個(gè)絕佳的練手材料。它不要求你掌握特別高深的知識但能讓你深刻理解叉積的符號意義并體會不同算法策略帶來的效率差異。接下來我就結(jié)合自己多次解題和教學(xué)的經(jīng)驗(yàn)把這背后的門道掰開揉碎了講清楚。2. 問題核心與幾何建模解析2.1 問題場景還原與抽象題目的描述非常形象有一個(gè)大長方形箱子從左到右被若干塊豎直的隔板分割成了若干個(gè)區(qū)域。這些隔板的上端和下端分別頂在箱子的上邊界和下邊界上但它們的橫坐標(biāo)是依次遞增的。然后我們會隨機(jī)往箱子里扔一些玩具抽象為平面上的點(diǎn)。我們的任務(wù)就是對于每一個(gè)玩具點(diǎn)判斷它落在了哪個(gè)隔板區(qū)間內(nèi)。這聽起來就像是一個(gè)兒童游樂場的收納問題但在計(jì)算機(jī)看來我們需要建立一個(gè)精確的數(shù)學(xué)模型。首先我們將整個(gè)場景放置在一個(gè)二維笛卡爾坐標(biāo)系中。通常我們會將箱子的左下角設(shè)為原點(diǎn)(0, 0)右上角設(shè)為(X, Y)。那么n塊隔板就對應(yīng)著n條線段。每條線段連接兩個(gè)點(diǎn)上端點(diǎn)(Ui, Y)和下端點(diǎn)(Li, 0)并且滿足Li和Ui都是嚴(yán)格遞增的即隔板不會交叉從左到右排列。這樣n塊隔板就將箱子分割成了n1個(gè)區(qū)域從左到右編號為0到n。給定m個(gè)玩具點(diǎn)的坐標(biāo)(x, y)我們需要輸出每個(gè)區(qū)域最終落入了多少個(gè)玩具。注意輸入數(shù)據(jù)通常保證玩具點(diǎn)不會恰好落在隔板線段上也不會落在箱子邊界之外。這是一個(gè)非常重要的簡化條件避免了處理邊界情況的麻煩讓我們可以專注于核心算法邏輯。2.2 核心工具向量叉積的符號意義解決這個(gè)問題的鑰匙就是向量的叉積。對于二維向量a (x1, y1)和b (x2, y2)它們的叉積在二維中常指標(biāo)量叉積或外積定義為a × b x1*y2 - y1*x2。這個(gè)數(shù)值的幾何意義非常強(qiáng)大絕對值表示以a和b為鄰邊構(gòu)成的平行四邊形的有向面積。符號這是我們本題最關(guān)心的。它表示向量b相對于向量a的旋轉(zhuǎn)方向。如果a × b 0說明b在a的逆時(shí)針方向左手系則為順時(shí)針。如果a × b 0說明b在a的順時(shí)針方向。如果a × b 0說明a和b共線方向相同或相反。如何應(yīng)用到我們的問題呢對于任意一個(gè)玩具點(diǎn)P(x, y)和一塊隔板線段ABA為上端點(diǎn)B為下端點(diǎn)我們可以構(gòu)造兩個(gè)向量向量AB從隔板上端點(diǎn)指向下端點(diǎn)即(L - U, 0 - Y) (L-U, -Y)。向量AP從隔板上端點(diǎn)指向玩具點(diǎn)即(x - U, y - Y)。計(jì)算叉積CP AB × AP。其符號的幾何意義可以理解為點(diǎn)P相對于有向線段AB的位置。如果CP 0點(diǎn)P在AB的左側(cè)以A為起點(diǎn)B為終點(diǎn)看。如果CP 0點(diǎn)P在AB的右側(cè)。為什么你可以把AB想象成面前的一條垂直參考線。AB × AP 0意味著AP向量相對于AB向量是逆時(shí)針旋轉(zhuǎn)的對于豎直向下的AB來說AP要逆時(shí)針轉(zhuǎn)那P點(diǎn)自然就在AB的左邊了。反之亦然。這個(gè)判斷是整個(gè)問題求解的基石。對于一塊隔板我們知道它左邊的區(qū)域編號是i-1右邊是i。如果我們能判斷點(diǎn)P在某塊隔板的右邊那就說明它至少不在編號小于i的區(qū)域里它可能位于i,i1, ... 這些區(qū)域。我們的任務(wù)就是為每個(gè)點(diǎn)找到最左邊的那塊隔板使得點(diǎn)P位于它的右側(cè)那么這個(gè)點(diǎn)就屬于這塊隔板右邊的那個(gè)區(qū)域。3. 解法一暴力遍歷法——最直觀的入門實(shí)現(xiàn)3.1 算法思路與實(shí)現(xiàn)步驟暴力法的思想直接源于上述幾何判斷對于每一個(gè)玩具點(diǎn)我們從左到右從第1塊到第n塊隔板依次檢查。對于第i塊隔板計(jì)算點(diǎn)P相對于它的位置。如果點(diǎn)P在第i塊隔板的左側(cè)CP 0說明點(diǎn)P還沒有越過這塊隔板它應(yīng)該位于第i-1個(gè)區(qū)域。此時(shí)我們可以停止遍歷記錄結(jié)果。如果點(diǎn)P在第i塊隔板的右側(cè)CP 0說明點(diǎn)P已經(jīng)在這塊隔板的右邊了我們繼續(xù)檢查下一塊隔板。如果我們檢查完了所有n塊隔板點(diǎn)P都在它們的右側(cè)那么這個(gè)點(diǎn)就落在了最右邊的第n個(gè)區(qū)域。實(shí)操步驟數(shù)據(jù)讀取與存儲讀入箱子右上角坐標(biāo)X, Y隔板數(shù)量n玩具數(shù)量m。然后讀入n塊隔板的上下端點(diǎn)橫坐標(biāo)Ui和Li通常存儲為兩個(gè)數(shù)組up[n]和low[n]。接著讀入m個(gè)玩具點(diǎn)的坐標(biāo)(x, y)。初始化計(jì)數(shù)數(shù)組創(chuàng)建一個(gè)大小為n1的數(shù)組cnt初始化為0用于記錄每個(gè)區(qū)域的玩具數(shù)量。遍歷每個(gè)玩具點(diǎn)對第j個(gè)玩具點(diǎn)(x, y) a. 設(shè)置一個(gè)變量region 0這是默認(rèn)區(qū)域最左邊如果點(diǎn)在所有隔板右側(cè)則最終區(qū)域就是n。 b. 循環(huán)i從0到n-1對應(yīng)第1到第n塊隔板 i. 計(jì)算向量AB (low[i] - up[i], -Y)。 ii. 計(jì)算向量AP (x - up[i], y - Y)。 iii. 計(jì)算叉積cross AB.x * AP.y - AB.y * AP.x。 iv. 如果cross 0說明點(diǎn)在當(dāng)前隔板左側(cè)跳出循環(huán)此時(shí)region的值i就是目標(biāo)區(qū)域編號。 v. 如果cross 0說明點(diǎn)在當(dāng)前隔板右側(cè)region自增1繼續(xù)檢查下一塊隔板。 c. 循環(huán)結(jié)束后region的值即為該玩具點(diǎn)所在區(qū)域編號0 到 n。執(zhí)行cnt[region]。輸出結(jié)果按照格式輸出cnt[0]到cnt[n]的值。3.2 代碼實(shí)現(xiàn)片段與關(guān)鍵點(diǎn)#include iostream #include cstring using namespace std; struct Point { int x, y; Point(int _x0, int _y0): x(_x), y(_y) {} }; // 計(jì)算叉積 (b-a) × (c-a) int cross(const Point a, const Point b, const Point c) { return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); } int main() { int n, m; int X1, Y1, X2, Y2; // 箱子左上角和右下角但通常我們只需要Y1上, Y2下 int U[5005], L[5005]; // 假設(shè)n最大5000 Point toys[5005]; int cnt[5005] {0}; while (cin n n) { cin m X1 Y1 X2 Y2; for (int i 0; i n; i) { cin U[i] L[i]; // 上端點(diǎn)和下端點(diǎn)x坐標(biāo) } for (int i 0; i m; i) { cin toys[i].x toys[i].y; } // 處理每個(gè)玩具 for (int i 0; i m; i) { Point p toys[i]; int region 0; // 遍歷每一塊隔板 for (int j 0; j n; j) { Point a(U[j], Y1); // 隔板上端點(diǎn) Point b(L[j], Y2); // 隔板下端點(diǎn) // 計(jì)算叉積判斷點(diǎn)p在向量ab的左側(cè)還是右側(cè) // 注意這里用a, b, p的順序計(jì)算的是 (b-a)×(p-a) // 如果結(jié)果 0則p在ab左側(cè)屬于當(dāng)前region if (cross(a, b, p) 0) { break; // 找到所屬區(qū)域跳出循環(huán) } else { region; // 點(diǎn)在右側(cè)區(qū)域編號1 } } cnt[region]; } // 輸出結(jié)果 for (int i 0; i n; i) { cout i : cnt[i] endl; } cout endl; memset(cnt, 0, sizeof(cnt)); // 多組數(shù)據(jù)清空計(jì)數(shù)器 } return 0; }關(guān)鍵點(diǎn)與注意事項(xiàng)叉積函數(shù)的設(shè)計(jì)我習(xí)慣實(shí)現(xiàn)一個(gè)計(jì)算(b-a)×(c-a)的函數(shù)這樣參數(shù)意義明確點(diǎn)a是向量起點(diǎn)b是第一個(gè)向量終點(diǎn)c是第二個(gè)向量終點(diǎn)。在本題中a是隔板上端點(diǎn)b是隔板下端點(diǎn)c是玩具點(diǎn)。判斷cross(a, b, p) 0即點(diǎn)p在向量ab左側(cè)。坐標(biāo)與方向務(wù)必注意題目給出的Y1和Y2哪個(gè)是上邊界哪個(gè)是下邊界。通常Y1 Y2因?yàn)閅坐標(biāo)向下增長。這會影響向量AB的y分量計(jì)算。在上面的代碼中a(U[j], Y1),b(L[j], Y2)所以AB (L[j]-U[j], Y2-Y1)由于Y2-Y1為負(fù)向量是向下的這與我們“從上到下”的隔板方向一致。循環(huán)終止條件暴力法的內(nèi)層循環(huán)可能提前跳出當(dāng)找到區(qū)域時(shí)平均來看效率尚可但在最壞情況下所有點(diǎn)都在最右邊區(qū)域每個(gè)點(diǎn)都要遍歷所有n塊隔板。4. 解法二二分查找法——效率的優(yōu)化4.1 優(yōu)化動機(jī)與可行性分析暴力法的時(shí)間復(fù)雜度是O(m * n)在n和m都達(dá)到5000量級時(shí)計(jì)算量是2500萬在POJ的舊評測機(jī)上可能處于超時(shí)的邊緣或者需要優(yōu)化常數(shù)。我們注意到一個(gè)關(guān)鍵性質(zhì)隔板的橫坐標(biāo)是嚴(yán)格遞增的。這意味著對于一個(gè)給定的玩具點(diǎn)P它相對于這些隔板的位置關(guān)系是“單調(diào)”的。想象一下從左到右掃描隔板點(diǎn)P開始時(shí)可能在某塊隔板左側(cè)CP 0隨著隔板越來越靠右點(diǎn)P終將變?yōu)樵谄溆覀?cè)CP 0。并且這個(gè)變化是一次性的不會出現(xiàn)左右搖擺的情況因?yàn)楦舭迨侵本€且點(diǎn)不在隔板上。更準(zhǔn)確地說函數(shù)f(i) sign( cross( a_i, b_i, P ) )是一個(gè)關(guān)于隔板索引i的單調(diào)非遞減函數(shù)值從1或0變?yōu)?1。這完美符合二分查找的應(yīng)用條件在一個(gè)有序序列中尋找一個(gè)邊界使得邊界左側(cè)滿足某個(gè)條件點(diǎn)P在隔板右側(cè)邊界右側(cè)不滿足該條件點(diǎn)P在隔板左側(cè)。我們要找的就是最左邊的那個(gè)使得點(diǎn)P在其左側(cè)的隔板這個(gè)隔板的索引i就對應(yīng)點(diǎn)P的區(qū)域編號i如果從0開始計(jì)數(shù)隔板。如果所有隔板都滿足點(diǎn)在其右側(cè)則區(qū)域編號為n。4.2 二分查找的實(shí)現(xiàn)細(xì)節(jié)二分查找的區(qū)間通常設(shè)為[0, n]其中n是隔板數(shù)量。我們需要定義判斷條件。設(shè)當(dāng)前檢查的隔板索引為mid。如果點(diǎn)P在第mid塊隔板的右側(cè)cross(a_mid, b_mid, P) 0說明目標(biāo)隔板點(diǎn)P左側(cè)的隔板還在更右邊我們應(yīng)該搜索右半?yún)^(qū)間[mid1, high]。如果點(diǎn)P在第mid塊隔板的左側(cè)cross(a_mid, b_mid, P) 0說明當(dāng)前隔板可能就是目標(biāo)或者目標(biāo)在左邊我們應(yīng)該搜索左半?yún)^(qū)間[low, mid]。注意這里不能是mid-1因?yàn)閙id本身可能是答案。我們最終要找到的是第一個(gè)使得點(diǎn)P在其左側(cè)的隔板索引。標(biāo)準(zhǔn)的二分查找模板尋找左邊界如下int binarySearch(const Point p, int n, int U[], int L[], int Y1, int Y2) { int low 0, high n; // 注意 high 初始為 n表示可能的結(jié)果范圍是 [0, n] while (low high) { int mid low (high - low) / 2; Point a(U[mid], Y1); Point b(L[mid], Y2); if (cross(a, b, p) 0) { // 點(diǎn)p在隔板mid右側(cè)目標(biāo)區(qū)域在右邊 low mid 1; } else { // 點(diǎn)p在隔板mid左側(cè)或共線題目保證不共線目標(biāo)區(qū)域可能是mid或左邊 high mid; } } // 循環(huán)結(jié)束時(shí)low high即為所求的區(qū)域編號 // 解釋low 是第一個(gè)滿足 cross 0 的隔板索引即點(diǎn)p在其左側(cè)的隔板。 // 這個(gè)索引值正好就是區(qū)域編號。例如第一個(gè)左側(cè)隔板是i則點(diǎn)落在i號區(qū)域。 return low; }對返回值low的理解二分查找結(jié)束后low的值表示點(diǎn)P在low號隔板的左側(cè)而在low-1號隔板的右側(cè)。因此點(diǎn)P就落在了low號區(qū)域。特別地如果low n說明點(diǎn)P在所有n塊隔板的右側(cè)因此落在第n號區(qū)域。這與暴力法的邏輯完全一致。4.3 復(fù)雜度對比與適用場景暴力法時(shí)間復(fù)雜度O(m * n)空間復(fù)雜度O(n m)。代碼極其簡單不易出錯(cuò)非常適合在時(shí)間限制寬松、或者n, m較小時(shí)例如均小于1000作為首選。在面試或快速原型驗(yàn)證時(shí)先寫出暴力法確保邏輯正確也是一個(gè)好習(xí)慣。二分法時(shí)間復(fù)雜度O(m * log n)空間復(fù)雜度O(n m)。在n較大時(shí)如5000log2(5000) ≈ 13效率提升非常顯著m*n的2500萬次計(jì)算降至m*log n的約65000次計(jì)算完全避免了超時(shí)風(fēng)險(xiǎn)。如何選擇追求效率與通用性毫無疑問選擇二分法。這是計(jì)算幾何中利用單調(diào)性進(jìn)行優(yōu)化的典型范例掌握它對于解決更復(fù)雜的問題如點(diǎn)在多邊形內(nèi)的判斷、凸包等有啟發(fā)意義。初學(xué)與調(diào)試可以先實(shí)現(xiàn)暴力法用其生成的數(shù)據(jù)對二分法進(jìn)行對拍測試確保二分查找的邊界條件完全正確。注意點(diǎn)二分法的實(shí)現(xiàn)需要格外小心邊界條件。上面的模板中初始high n以及循環(huán)條件while (low high)和high mid的賦值是處理“尋找左邊界”問題的常見寫法需要理解其含義死記硬背容易出錯(cuò)。5. 實(shí)戰(zhàn)中的常見問題與深度排查即便理解了算法在實(shí)現(xiàn)時(shí)還是會遇到一些“坑”。下面是我在多次解題和教學(xué)中總結(jié)出來的常見問題。5.1 叉積計(jì)算與方向判斷錯(cuò)誤這是最常見的問題。核心在于向量構(gòu)造的順序和叉積公式的應(yīng)用。問題表現(xiàn)所有點(diǎn)都被判到同一個(gè)區(qū)域如最左邊或最右邊或者結(jié)果看起來隨機(jī)混亂。排查步驟確認(rèn)向量起點(diǎn)確保你計(jì)算的叉積是(隔板向量) × (點(diǎn)到起點(diǎn)的向量)。常見的函數(shù)是cross(a, b, p)計(jì)算(b-a)×(p-a)。這里的a必須是隔板的上端點(diǎn)。確認(rèn)坐標(biāo)對應(yīng)檢查你傳入的Y1和Y2是否與點(diǎn)的y坐標(biāo)在同一個(gè)坐標(biāo)系下。比如題目輸入可能是Y1為上Y2為下那么a.y Y1,b.y Y2。如果搞反了向量的方向就反了叉積符號也就反了。手工驗(yàn)證找一個(gè)簡單例子比如只有一塊隔板在x5的位置箱子上下邊界為0和10。分別取點(diǎn)(2, 5)應(yīng)在左側(cè)和(8, 5)應(yīng)在右側(cè)手工計(jì)算叉積看符號是否符合你的判斷邏輯0左還是0左。我的心得統(tǒng)一使用一個(gè)經(jīng)過測試的cross函數(shù)并明確其幾何意義cross(a,b,c)0表示c在ab左側(cè)。在題目中固定使用一種判斷標(biāo)準(zhǔn)不要混用。5.2 二分查找的邊界條件陷阱二分查找的細(xì)節(jié)決定成敗。問題表現(xiàn)部分點(diǎn)區(qū)域判斷錯(cuò)誤尤其是在邊緣區(qū)域0區(qū)或n區(qū)。排查步驟初始區(qū)間為什么high初始是n而不是n-1因?yàn)榇鸢缚赡苁莕點(diǎn)在所有隔板右側(cè)。搜索區(qū)間[0, n]是左閉右開[low, high)的表示high初始值n表示有效的索引范圍是0到n-1但n本身作為一個(gè)可能的答案表示“第n個(gè)區(qū)域”需要被包含在搜索空間中。在循環(huán)中我們通過mid訪問隔板數(shù)組時(shí)mid的范圍是[0, n-1]當(dāng)low被推到n時(shí)循環(huán)結(jié)束n就是答案。循環(huán)條件與更新while (low high)確保退出時(shí)low high。當(dāng)cross 0點(diǎn)在右側(cè)時(shí)答案一定在mid右邊所以low mid 1。當(dāng)cross 0點(diǎn)在左側(cè)時(shí)mid可能是答案所以high mid保留mid在區(qū)間內(nèi)。測試用例構(gòu)造極端數(shù)據(jù)測試。例如沒有隔板n0點(diǎn)應(yīng)該全部落在區(qū)域0。只有一塊隔板點(diǎn)分別在左右側(cè)。所有點(diǎn)都在最左或最右區(qū)域。我的心得理解二分查找的“區(qū)間不變式”。在上述寫法中循環(huán)不變式是答案區(qū)域編號一定在區(qū)間[low, high)內(nèi)。初始化時(shí)區(qū)間是[0, n)包含了所有可能答案。每次循環(huán)根據(jù)mid處的判斷我們將答案不可能存在的半邊區(qū)間排除并保持答案仍在新的[low, high)區(qū)間內(nèi)。當(dāng)區(qū)間縮小到只有一個(gè)元素 (low high) 時(shí)那個(gè)位置就是答案。5.3 多組數(shù)據(jù)輸入的初始化問題POJ的題目經(jīng)常有多組測試數(shù)據(jù)直到輸入n0為止。問題表現(xiàn)第二組數(shù)據(jù)的結(jié)果被第一組數(shù)據(jù)污染輸出錯(cuò)誤。解決方案在每處理完一組數(shù)據(jù)后必須清空用于計(jì)數(shù)的數(shù)組cnt。使用memset(cnt, 0, sizeof(cnt))或循環(huán)歸零。注意如果使用C的vector需要在讀取新的n后resize(n1)并賦零。額外提醒注意題目輸出的格式每組數(shù)據(jù)結(jié)果后面有時(shí)需要跟一個(gè)空行。仔細(xì)閱讀輸出說明。6. 從TOYS問題延伸的思考與技巧解決POJ 2318不僅僅是為了AC一道題更是為了掌握一類思想。6.1 叉積判斷點(diǎn)與線關(guān)系的通用性本題利用叉積判斷點(diǎn)在有向線段的左右側(cè)這是計(jì)算幾何中最基礎(chǔ)、最常用的操作之一。這個(gè)技巧可以推廣到許多問題線段相交判斷快速排斥實(shí)驗(yàn)后利用叉積檢查兩點(diǎn)是否在線段兩側(cè)。凸多邊形包含點(diǎn)判斷依次判斷點(diǎn)是否在多邊形每條邊的同一側(cè)例如左側(cè)如果是則在多邊形內(nèi)。極角排序以某個(gè)點(diǎn)為基點(diǎn)計(jì)算其他點(diǎn)相對于該點(diǎn)的向量的叉積用于排序。理解其本質(zhì)叉積的符號反映了兩個(gè)向量的“旋轉(zhuǎn)方向”從而可以建立“方向”和“位置”的聯(lián)系。6.2 二分查找的單調(diào)性來源本題二分可行的根本原因是隔板的有序性Ui和Li遞增導(dǎo)致了位置判斷函數(shù)的單調(diào)性。在實(shí)際問題中如何發(fā)現(xiàn)并利用這種單調(diào)性是一種重要的解題能力。例如在一些最優(yōu)化問題中如果決策函數(shù)是單調(diào)的就可以用二分法來枚舉答案將最優(yōu)化問題轉(zhuǎn)化為判定問題。6.3 浮點(diǎn)數(shù)處理的注意事項(xiàng)本題輸入坐標(biāo)是整數(shù)所以用整數(shù)計(jì)算叉積完全沒問題避免了浮點(diǎn)數(shù)精度誤差。但如果坐標(biāo)是浮點(diǎn)數(shù)在判斷cross 0或cross 0時(shí)就不能直接與0比較而應(yīng)該與一個(gè)極小的精度容忍值eps如1e-10比較。例如if (cross eps)判斷為正if (cross -eps)判斷為負(fù)否則認(rèn)為共線。在POJ 2318中明確點(diǎn)不在隔板上整數(shù)計(jì)算足夠安全但養(yǎng)成這個(gè)意識對處理其他計(jì)算幾何題目至關(guān)重要。6.4 調(diào)試與對拍策略對于這類問題高效的調(diào)試策略能節(jié)省大量時(shí)間。小數(shù)據(jù)手工模擬畫出坐標(biāo)系標(biāo)出隔板和幾個(gè)測試點(diǎn)手工計(jì)算叉積和區(qū)域與程序輸出對比。暴力法對拍這是最有效的方法。先寫一個(gè)絕對正確的暴力解法O(n*m)再寫優(yōu)化算法二分法。用隨機(jī)生成的大量數(shù)據(jù)注意保證點(diǎn)不在隔板上同時(shí)運(yùn)行兩個(gè)程序?qū)Ρ容敵?。POJ的n, m最多5000在本地生成數(shù)據(jù)對拍很容易。邊界測試專門生成n0,n1,m0如果允許以及點(diǎn)緊貼隔板但不相交的數(shù)據(jù)進(jìn)行測試。最后這道題看似簡單卻涵蓋了計(jì)算幾何的基石思想、基礎(chǔ)算法的優(yōu)化策略以及嚴(yán)謹(jǐn)?shù)拇a實(shí)現(xiàn)細(xì)節(jié)。我建議在理解的基礎(chǔ)上能夠不參考任何代碼獨(dú)立完成從暴力到二分的兩種實(shí)現(xiàn)并通過在線評測系統(tǒng)進(jìn)行提交驗(yàn)證。這個(gè)過程收獲的遠(yuǎn)不止一個(gè)“Accepted”。