1. 這道題到底在考什么線性分類器這個題目第一次看到的時候我差點笑出聲——這不就是高中解析幾何里直線方程和點位置關(guān)系的翻版嗎但仔細(xì)一琢磨這道題放在CSP認(rèn)證的第二題位置確實有它的道理。它不考你什么高深的算法也不要求你寫復(fù)雜的動態(tài)規(guī)劃它考的是你能不能把實際問題轉(zhuǎn)化成數(shù)學(xué)模型然后用代碼老老實實實現(xiàn)出來。先說說這個題目的背景。CSP認(rèn)證是中國計算機(jī)學(xué)會辦的軟件能力認(rèn)證一共五道題難度遞增。第一題通常是簽到題第二題就是這種需要動點腦筋但代碼量不大的題目。線性分類器出現(xiàn)在第十九次認(rèn)證里當(dāng)時考完之后網(wǎng)上討論度挺高因為很多人第一眼看過去覺得簡單結(jié)果提交之后發(fā)現(xiàn)只過了部分測試點。題目大意是這樣的給你一堆二維平面上的點每個點要么是A類要么是B類。然后給你若干條直線每條直線用三個參數(shù)表示問這條直線能不能把A類和B類點完美分開——也就是說所有A類點都在直線的一側(cè)所有B類點都在直線的另一側(cè)。注意題目保證不會有點落在直線上。這個問題的核心其實就一個公式對于直線AxByC0把點(x0,y0)代入得到Ax0By0C。如果結(jié)果大于0說明點在直線的一側(cè)小于0在另一側(cè)。你只需要檢查所有A類點的符號是否一致所有B類點的符號是否一致并且A類和B類的符號相反就行了。聽起來是不是特別簡單但這里有幾個坑我當(dāng)年第一次做的時候全踩了一遍。第一個坑是數(shù)據(jù)類型坐標(biāo)和參數(shù)的范圍可能很大代入之后的結(jié)果可能超出int的范圍必須用long long。第二個坑是符號判斷的邏輯不能只判斷A類點符號一致就完事了還得確認(rèn)B類點符號也一致并且兩類符號相反。第三個坑是讀題要仔細(xì)題目說的是“完美分開”意味著不能有任何例外。我后來跟幾個也在準(zhǔn)備CSP的朋友聊過發(fā)現(xiàn)大家犯的錯誤出奇地一致。有人忘了用long long導(dǎo)致溢出有人只檢查了一類點的符號還有人把直線方程的參數(shù)順序搞混了。這些錯誤單獨拿出來看都很低級但在考場上時間壓力下真的很容易犯。這道題適合什么人看如果你正在準(zhǔn)備CSP認(rèn)證那這道題是必刷的因為它代表了第二題的標(biāo)準(zhǔn)難度和出題風(fēng)格。如果你剛開始學(xué)C語言想找一道能練手的題目這道題也很合適它涉及了基本的輸入輸出、循環(huán)、條件判斷和簡單的數(shù)學(xué)知識。如果你已經(jīng)工作多年想回顧一下基礎(chǔ)算法題這道題也能讓你找回一些手感。接下來我會從題目分析、數(shù)學(xué)原理、代碼實現(xiàn)、常見錯誤和優(yōu)化技巧幾個方面把這道題徹底講透。我會盡量用大白話把每個細(xì)節(jié)都說清楚讓你看完之后不僅能AC這道題還能掌握這一類題目的通用解法。2. 從數(shù)學(xué)原理到代碼邏輯的完整拆解2.1 直線方程與點位置關(guān)系的數(shù)學(xué)基礎(chǔ)咱們先從最根本的數(shù)學(xué)原理說起。二維平面上的直線一般式方程是AxByC0其中A、B不同時為0。這個方程看起來簡單但它包含了直線的所有信息。A和B決定了直線的方向C決定了直線的位置。對于平面上的任意一點(x0,y0)把它代入直線方程得到的結(jié)果Ax0By0C有三種可能大于0、等于0、小于0。大于0和小于0分別代表點在直線的兩側(cè)等于0代表點在直線上。這個結(jié)論的幾何意義是直線把整個平面分成了兩個半平面每個半平面里的點代入方程后符號是一致的。為什么會有這個性質(zhì)你可以這樣理解直線方程本質(zhì)上是一個線性函數(shù)f(x,y)AxByC。線性函數(shù)有一個重要性質(zhì)就是它的等值線是平行的直線。f(x,y)0就是那條分界線f(x,y)0的區(qū)域和f(x,y)0的區(qū)域被這條線隔開。當(dāng)你從直線的一側(cè)走到另一側(cè)時必然要穿過直線在穿過的那一瞬間函數(shù)值從正變負(fù)或從負(fù)變正中間必然經(jīng)過0。這個性質(zhì)就是線性分類器的理論基礎(chǔ)。所謂線性分類器就是用一條直線在高維空間里是超平面把不同類別的數(shù)據(jù)點分開。在二維平面上就是找一條直線使得一類點全在直線一側(cè)另一類點全在另一側(cè)。題目里說“保證不會有點落在直線上”這個條件很重要。如果有點落在直線上代入結(jié)果是0那這個點既不在正側(cè)也不在負(fù)側(cè)分類就失敗了。題目把這個情況排除掉我們就不用處理等于0的特殊情況代碼可以簡化一些。2.2 如何判斷一條直線能否完美分類現(xiàn)在問題轉(zhuǎn)化為給定一條直線和一堆帶類別的點怎么判斷這條直線能不能完美分類思路很直接把所有A類點代入直線方程看看結(jié)果是不是全為正或者全為負(fù)把所有B類點也代入看看結(jié)果是不是全為另一種符號。如果A類點全為正且B類點全為負(fù)或者A類點全為負(fù)且B類點全為正那這條直線就能完美分類。但這里有個細(xì)節(jié)需要注意我們不能只檢查A類點的符號是否一致還要檢查B類點的符號是否一致并且兩類符號必須相反。舉個例子假設(shè)A類點代入后全是正數(shù)B類點代入后也全是正數(shù)那說明兩類點在直線的同一側(cè)分類失敗。再假設(shè)A類點代入后有正有負(fù)那說明A類點自己都沒法用這條直線統(tǒng)一到一側(cè)分類也失敗。所以完整的判斷邏輯是計算第一個A類點的符號記為signA。遍歷所有A類點如果某個點的符號和signA不同返回失敗。計算第一個B類點的符號記為signB。遍歷所有B類點如果某個點的符號和signB不同返回失敗。如果signA和signB相同返回失敗否則返回成功。這個邏輯看起來簡單但寫代碼的時候容易漏掉步驟。我見過有人只做了第2步和第4步忘了第5步結(jié)果兩類點在同一側(cè)的情況也被判為成功。也見過有人只檢查了A類點覺得B類點自動就滿足條件了這顯然是不對的。2.3 數(shù)據(jù)類型的選擇與溢出問題這道題最容易被忽視的坑就是數(shù)據(jù)類型。題目里點的坐標(biāo)和直線的參數(shù)范圍雖然沒有明確給出但根據(jù)CSP的慣例這些值可能在-10^6到10^6之間。代入直線方程后Ax0By0C的結(jié)果可能達(dá)到10^12級別這遠(yuǎn)遠(yuǎn)超出了int的范圍約2×10^9。如果你用int來存計算結(jié)果就會發(fā)生溢出。溢出的后果是符號可能翻轉(zhuǎn)本來正數(shù)變成負(fù)數(shù)本來負(fù)數(shù)變成正數(shù)導(dǎo)致判斷完全錯誤。更可怕的是這種錯誤不是必然發(fā)生的而是取決于具體的數(shù)值。你可能在本地測試的時候用的數(shù)據(jù)比較小沒有觸發(fā)溢出提交上去之后被大數(shù)據(jù)測試點卡掉還找不到原因。所以這道題必須用long long來存計算結(jié)果。long long的范圍大約是-9×10^18到9×10^18足夠容納10^12級別的結(jié)果。在C語言里long long的輸入輸出格式是%lld這一點也要注意用錯了會導(dǎo)致讀入錯誤。我當(dāng)年第一次做的時候就是栽在這個坑上。本地測試全過提交之后只過了前幾個測試點后面全WA。查了半天才發(fā)現(xiàn)是int溢出。從那以后我做任何涉及乘法或者大數(shù)加法的題目都會先估算一下結(jié)果的范圍不確定就用long long。2.4 輸入輸出的處理細(xì)節(jié)CSP的題目輸入輸出格式通常比較固定但也有一些細(xì)節(jié)需要注意。這道題的輸入格式大概是這樣的第一行兩個整數(shù)n和mn是點的數(shù)量m是直線的數(shù)量。接下來n行每行兩個整數(shù)x和y以及一個字符表示類別A或B。再接下來m行每行三個整數(shù)A、B、C表示一條直線。讀入的時候有幾個點要注意。首先是字符的讀入用scanf讀字符的時候%c會讀入空格和換行符所以通常要在%c前面加一個空格寫成 %c這樣可以跳過空白字符。其次是多組數(shù)據(jù)的處理這道題有m條直線每條直線都要獨立判斷所以需要把點的信息存下來然后對每條直線重新遍歷所有點。輸出格式通常是每行一個Yes或No注意大小寫要和題目要求一致。CSP的題目有時候要求輸出Yes和No有時候要求輸出YES和NO這個一定要看清楚。我見過有人因為大小寫問題WA了好幾次這種錯誤真的很冤。還有一個細(xì)節(jié)是數(shù)組的大小。n和m的范圍題目里會給但有時候給的是上限你需要根據(jù)上限來定義數(shù)組大小。如果數(shù)組開小了會越界訪問可能導(dǎo)致程序崩潰或者結(jié)果錯誤。通常我會在題目給的上限基礎(chǔ)上再加10個元素的余量防止邊界情況出問題。3. 完整代碼實現(xiàn)與逐行解析3.1 代碼整體框架先來看完整的代碼框架。我用C語言寫因為題目要求就是C語言。代碼結(jié)構(gòu)很清晰定義結(jié)構(gòu)體存點讀入數(shù)據(jù)對每條直線遍歷所有點判斷符號輸出結(jié)果。#include stdio.h typedef struct { long long x; long long y; char type; } Point; Point points[1005]; int main() { int n, m; scanf(%d %d, n, m); for (int i 0; i n; i) { scanf(%lld %lld %c, points[i].x, points[i].y, points[i].type); } for (int i 0; i m; i) { long long A, B, C; scanf(%lld %lld %lld, A, B, C); int signA 0, signB 0; int valid 1; for (int j 0; j n; j) { long long result A * points[j].x B * points[j].y C; int sign (result 0) ? 1 : -1; if (points[j].type A) { if (signA 0) { signA sign; } else if (signA ! sign) { valid 0; break; } } else { if (signB 0) { signB sign; } else if (signB ! sign) { valid 0; break; } } } if (valid signA ! 0 signB ! 0 signA ! signB) { printf(Yes\n); } else { printf(No\n); } } return 0; }這段代碼看起來不長但每一行都有講究。下面我逐段拆解。3.2 結(jié)構(gòu)體定義與數(shù)據(jù)存儲我用了一個結(jié)構(gòu)體Point來存每個點的信息包括x坐標(biāo)、y坐標(biāo)和類別。x和y用long long是因為坐標(biāo)本身可能很大雖然坐標(biāo)本身不太可能超過int范圍但為了保險起見用long long更穩(wěn)妥。類別用char存A或B。數(shù)組大小我開了1005因為題目里n的上限通常是1000加5個余量防止越界。這個習(xí)慣很重要我見過太多人因為數(shù)組開小了一點點導(dǎo)致各種奇怪的問題。有朋友可能會問為什么不把點的x和y分開存兩個數(shù)組其實都可以用結(jié)構(gòu)體更直觀一些代碼可讀性更好。在考場上代碼可讀性雖然不直接得分但能幫你減少犯錯。當(dāng)你調(diào)試的時候看到points[j].x比看到x[j]更容易理解。3.3 符號判斷的核心邏輯符號判斷是這道題的核心。我用signA和signB來記錄A類點和B類點的符號初始為0表示還沒遇到任何該類點。遍歷每個點時計算result Ax By C然后根據(jù)result的正負(fù)得到sign1或-1。如果當(dāng)前點是A類檢查signA如果signA為0說明這是第一個A類點把signA設(shè)為當(dāng)前符號如果signA不為0且和當(dāng)前符號不同說明A類點出現(xiàn)了不一致的符號分類失敗把valid設(shè)為0并跳出循環(huán)。B類點的處理同理。最后判斷valid為1且signA和signB都不為0且signA不等于signB才輸出Yes。這里有個細(xì)節(jié)signA ! 0 signB ! 0這個條件。理論上題目保證不會有點在直線上所以只要出現(xiàn)了A類點和B類點signA和signB就一定會被賦值。但萬一測試數(shù)據(jù)有問題或者你讀入的時候出了錯這個條件可以防止誤判。加上它更保險。還有一個細(xì)節(jié)是break的使用。當(dāng)發(fā)現(xiàn)符號不一致時直接break跳出循環(huán)不需要繼續(xù)檢查后面的點了。這樣可以節(jié)省時間雖然這道題的數(shù)據(jù)量不大不break也能過但養(yǎng)成好習(xí)慣總是好的。3.4 輸入輸出的注意事項輸入部分scanf的格式字符串要和數(shù)據(jù)類型匹配。long long用%lldint用%dchar用%c。特別注意%c前面要加空格否則會讀入上一行的換行符。輸出部分我用的是printf(Yes\n)和printf(No\n)。這里的大小寫要和題目要求一致。CSP的題目通常要求首字母大寫但不同題目可能不一樣一定要仔細(xì)看題。有朋友可能會問為什么不用bool類型C語言里bool需要包含stdbool.h而且本質(zhì)上還是int。我用int來表示valid0表示失敗1表示成功簡單明了。另外我把判斷邏輯寫在了主函數(shù)里沒有單獨寫函數(shù)。對于這種規(guī)模的題目寫不寫函數(shù)都可以。寫函數(shù)的好處是邏輯更清晰但會增加函數(shù)調(diào)用的開銷雖然可以忽略不計。在考場上我傾向于怎么快怎么寫只要邏輯正確就行。4. 常見錯誤與排查技巧實錄4.1 數(shù)據(jù)類型溢出最隱蔽的殺手?jǐn)?shù)據(jù)類型溢出是這道題的頭號殺手。我敢說第一次做這道題的人里至少有三分之一栽在這個坑上。問題出在Ax By C這個表達(dá)式上。A、x、B、y、C都可能是很大的數(shù)乘起來之后更大加起來可能超出int的范圍。int通常是32位范圍大約是-2.1×10^9到2.1×10^9。假設(shè)A和x都是10^6乘積就是10^12這已經(jīng)超出int范圍了。更不用說Ax By C三項加起來可能達(dá)到3×10^12。用int存這個結(jié)果溢出是必然的。溢出的后果是符號可能翻轉(zhuǎn)。比如一個很大的正數(shù)溢出后可能變成負(fù)數(shù)導(dǎo)致你判斷點在直線的一側(cè)實際上在另一側(cè)。這種錯誤在小數(shù)據(jù)下可能不出現(xiàn)因為小數(shù)據(jù)不會溢出。所以你本地測試全過提交上去就WA而且你還找不到原因。解決辦法很簡單把所有涉及坐標(biāo)和直線參數(shù)的變量都聲明為long long。包括點的x、y直線的A、B、C以及計算結(jié)果result。輸入輸出用%lld。這樣就不會溢出了。我后來總結(jié)了一個經(jīng)驗做任何CSP題目只要涉及乘法或者大數(shù)加法先估算一下結(jié)果的范圍。如果可能超過10^9就用long long。這個習(xí)慣幫我避免了很多類似的錯誤。4.2 符號判斷的邏輯漏洞符號判斷的邏輯漏洞是另一個常見錯誤。我見過幾種典型的錯誤寫法。第一種是只檢查了A類點的符號一致性忘了檢查B類點。這種錯誤的原因是思維定勢覺得A類點一致就行了B類點自然就一致。但實際上B類點可能自己就不一致或者和A類點符號相同。第二種是檢查了兩類點的符號一致性但忘了檢查兩類符號是否相反。這種錯誤更隱蔽因為代碼看起來是對的邏輯上卻漏了一步。兩類點各自符號一致但如果在同一側(cè)分類還是失敗的。第三種是初始值設(shè)置有問題。有人把signA初始化為1signB初始化為-1然后遍歷所有點檢查符號是否匹配。這種寫法在第一個點恰好匹配初始值的時候沒問題但如果第一個點不匹配就會誤判。正確的做法是用0表示未初始化遇到第一個點時再賦值。第四種是忘了處理沒有A類點或沒有B類點的情況。雖然題目通常保證兩類點都有但萬一測試數(shù)據(jù)里有只有一類點的情況你的代碼可能會出錯。加上signA ! 0 signB ! 0的判斷可以避免這個問題。4.3 輸入讀入的陷阱輸入讀入的陷阱主要有兩個字符讀入和格式匹配。字符讀入的問題前面提過%c會讀入空白字符。如果你寫scanf(%lld %lld %c, ...)在%c前面沒有空格那么當(dāng)輸入是1 2 A的時候%c會讀到空格而不是A。正確的寫法是scanf(%lld %lld %c, ...)在%c前面加一個空格這樣可以跳過所有空白字符。格式匹配的問題是long long必須用%lld不能用%d。用錯了會導(dǎo)致讀入的數(shù)據(jù)不正確而且這種錯誤很隱蔽因為程序不會崩潰只是數(shù)據(jù)錯了。你可能會看到一些莫名其妙的結(jié)果卻找不到原因。還有一個細(xì)節(jié)是如果輸入文件里有多余的空格或空行scanf通常能自動處理但%c是個例外。所以再次強(qiáng)調(diào)%c前面加空格。4.4 常見問題速查表問題現(xiàn)象可能原因排查方法解決方案本地測試通過提交WA數(shù)據(jù)類型溢出檢查是否用了long long把所有相關(guān)變量改為long long部分測試點WA符號判斷邏輯錯誤手動模擬幾個測試用例檢查是否漏了符號相反判斷程序崩潰或結(jié)果異常數(shù)組越界檢查數(shù)組大小是否足夠數(shù)組開大一些加余量讀入數(shù)據(jù)不正確格式字符串錯誤檢查scanf的格式long long用%lld%c前加空格輸出格式錯誤大小寫或換行問題仔細(xì)看題目要求嚴(yán)格按照題目要求輸出這張表里的問題我都遇到過有些還不止遇到過一次。每次犯錯之后我都會記下來下次做類似的題目就會特別注意。我覺得這個方法很有效推薦你也試試。5. 從這道題延伸出去的思考5.1 線性分類器的實際應(yīng)用雖然這道題只是CSP認(rèn)證里的一道算法題但線性分類器這個概念在實際中是有應(yīng)用的。機(jī)器學(xué)習(xí)里最簡單的分類器就是線性分類器比如感知機(jī)、邏輯回歸本質(zhì)上都是在找一條直線或超平面把數(shù)據(jù)分開。當(dāng)然實際應(yīng)用中的線性分類器要復(fù)雜得多。數(shù)據(jù)可能是高維的不是二維平面上的點分類邊界可能不是直線而是曲線數(shù)據(jù)可能不是完美可分的需要容忍一些錯誤分類。但核心思想是一樣的找一個線性函數(shù)讓不同類別的數(shù)據(jù)代入后符號不同。如果你對機(jī)器學(xué)習(xí)感興趣這道題可以作為一個起點。你可以想想如果數(shù)據(jù)不是完美可分的怎么辦如果要用代碼自動找到那條分類直線怎么辦這些問題就引出了更深入的算法比如梯度下降、支持向量機(jī)等。5.2 計算幾何題目的通用套路這道題屬于計算幾何的范疇。計算幾何的題目通常涉及點、線、面、多邊形等幾何對象以及它們之間的位置關(guān)系。這類題目的特點是數(shù)學(xué)原理不復(fù)雜但代碼實現(xiàn)容易出錯邊界情況多。做計算幾何題目我有幾個通用的經(jīng)驗。第一盡量用整數(shù)運(yùn)算避免浮點數(shù)。浮點數(shù)有精度問題可能導(dǎo)致判斷錯誤。這道題用整數(shù)運(yùn)算就很合適因為直線方程和點坐標(biāo)都是整數(shù)。第二注意數(shù)據(jù)范圍該用long long就用long long。第三多畫圖把各種情況都畫出來看看你的邏輯是否覆蓋了所有情況。第四寫完之后用幾個簡單的測試用例手動模擬一下確認(rèn)邏輯正確。5.3 考試策略與時間分配CSP認(rèn)證一共五道題考試時間四個小時。線性分類器通常是第二題難度中等。我的建議是第一題快速做完不要花太多時間。第二題仔細(xì)做確保拿滿分。第三題和第四題看情況如果時間夠就做不夠就放棄。第五題通常是難題除非你特別厲害否則不要在上面浪費(fèi)時間。做第二題的時候我通常會花五到十分鐘讀題和理解題意然后花十到十五分鐘寫代碼再花五到十分鐘測試和調(diào)試?？偣舶胄r左右。如果超過四十分鐘還沒做出來我會先跳過做后面的題目最后再回來做。這道題雖然不難但陷阱不少。我建議你在考場上先把所有可能的坑都想一遍數(shù)據(jù)類型、符號判斷、輸入格式、輸出格式。想清楚了再動手寫比寫完再調(diào)試要快得多。5.4 如何練習(xí)這類題目如果你想提高做這類題目的能力我的建議是多刷題但不要盲目刷。每做完一道題都要總結(jié)一下這道題考了什么知識點我犯了什么錯誤下次怎么避免這樣刷一道題的效果比刷十道題但不總結(jié)要好得多。具體到線性分類器這道題你可以先自己做一遍然后對照我的代碼看看有什么不同。如果你犯了錯誤想想為什么會犯是知識點不熟還是粗心大意。如果是知識點不熟就去補(bǔ)一下相關(guān)的數(shù)學(xué)知識。如果是粗心大意就提醒自己下次注意。你還可以把這道題改一改增加一些難度。比如如果有點落在直線上怎么辦如果要求輸出具體的分類結(jié)果怎么辦如果直線不是用一般式表示而是用兩點式表示怎么辦這些改動可以幫你更深入地理解這道題。我個人在實際操作中的體會是CSP認(rèn)證的題目雖然不難但很考驗基本功。那些看似簡單的題目往往藏著不少坑。只有把基本功練扎實了才能在考場上游刃有余。希望這篇博文能幫你少走一些彎路順利通過認(rèn)證。