現在有 N 堆，總共有 N 種物品，希望移動最少次，使得每一堆只具有單一種物品。
輸出最小的組合方案。按照第 i 種物品放置在第 j 堆的字典順序最小。
|
|
|
|
很明顯地答案會是在某一堆 X 指派給 A 物品，那麼可以減少的移動次數是 X 原本具有 A 的數量。因此答案會是物品述兩總和扣除最大權匹配。
但是答案特別要求輸出字典順序要最小，所以用 KM 算法、最少費用流會稍微麻煩一點，也許多做 $O(N^2)$ 次的窮舉也可以完成。這裡使用 bitmask 的方式去找到最順序最小的最大權匹配。
|
|
類似磁性場，所有的指針位置都會指向目的地。不過這題的感覺比較像是風向儀，從目的地往外吹動，三角形是風向儀所在的位置，正方形則表示旗幟飄揚的位置。
給定三角形位置，請問正方形的位置在哪裡。
|
|
|
|
測資參考圖
|
|
範例輸出有錯，一開始以為自己寫錯。
由於盤面不大，可以直接進行全盤著色，分成四個象限去著色。當然如果盤面大一點，則必須考慮用外積等方式去完成象限判斷。由於是網格狀，邊界上會比較麻煩，方便起見還是直接著色。
|
|
接續上一篇
調適能力 (Adaptivity) 與調適性 (Adaptability)。前者能依據使用者的互動 (interaction) 自動修改應用程式的行為，後者則是依照預先定義好的選項來改變應用程式的行為。
| 網頁設計類型 | 優點 | 缺點 |
|---|---|---|
| Adaptivity | 迅速地貼近使用者，使用者不必做過多設定 | 由於自動變化，對於使用者教學會相當困難 |
| Adaptability | 客製化過程有參與感，可以更了解系統功能 | 入門困難，適應介面到可以客製的過程長 |
|
|
從最基礎的設計中，明顯地會需要一個輸入框與觸發的按鈕。但是搜尋條件有幾種，從 作者 、 本文 、 標題 、 出版期刊 … 等，這些要怎麼設計才好？
《大神落伍了？這些搜索引擎比 Google 精確還更有趣》 這裡提到專門的搜尋引擎，可以針對音樂、圖片、社群、找人 … 等內容進行搜尋。他們是怎麼完成的？
|
|
這裡的設計多了三個欄位，有些欄位可填、可不填，進行分開的搜尋。然而會不會發生有人誤填一些資訊，誤把人名當書名，造成搜尋結果不好。為了考量這些，基本上都是在搜尋結果中做一個排序，排序的優先權可能先按照書名、作者、地點。搜尋方式的比例差異通常呈現普遍性。
為了加速篩選結果，通常會先抓書名，如果書名不夠具有特色，則會嘗試抓作者名稱，如果作者出版很多本書，則會考慮出版時間、內容。能按照內容進行搜索的引擎，肯定規模很大。
|
|
有一種方式是提供搜尋條件的細節，來增加使用者的搜尋效率。上面就是一個範例，不僅僅只是官方書名提供搜索，細節劃分也是相當重要。甚至有人會將書給予暱稱，例如書的名稱太普通，卻以某種封裝、寫法出名，那麼這些書的名稱可能就比較特別。
對於場依賴的而言，看得到的搜尋介面相當重要，它們比較容易根據環境提供的條件，因此設計效能上影響很多。反過來看看場獨立的人，對於這個介面操作可能會將自己的想法投入，這些想法可能來自於自身或者是之前學習過的知識。
|
|
對於隱藏式的操作想必也是相當上手。但這種使用需要教學，不是相當方便。可以由簡到繁地引領使用者，例如說第一次搜尋操作後，自動填充，提示使用者下一次搜尋的方法。
|
|
得到結果後
|
|
現在的設計大多都是由 簡到繁 的方式，從蘋果軟體中都可以發現到這些特徵，將不常用的功能都先藏在特定的地方，先基礎地提供最低需求，當使用者發現結果越來越不好時，主動地去察覺要怎麼使用更複雜的操作。
當然有些人搜尋的結果，會根據場依賴、場獨立來查閱，場依賴偏向是由觀眾評分、評論來判定是否找到正確的書，場獨立純文本內容為主。著重的觀點不同，為了成功銷售所有的書籍，顯示的方法如下兩種參考。
|
|
|
|
以上示範的是場獨立、依賴的兩種。當然上面的設計屬於階層式、也有水平擺放訊息的方式。其實還有很多種的！
|
|
|
|
如果找書不根據任何別人推坑的想法，階層式會是很好的細節來決策，嘗試把每一本書的概要都仔細讀過，階層式很吃 優先權順序 ，設計起來相當挑戰。
如果是下方的方式，比較偏向大致上已經在事前知道要買哪本書，有了大概目標。這樣的設計方式方便跳躍性的搜索，因為階層式會 改變高度 ，檢索時的位移量不同會造成操作時間會比較久，但是下方的那種方式屬於固定位移量。
至於對色彩學的配色部分，又分單色、雙色欄位，來加快視窗滑動的對齊。而每一個欄位的文字色彩也相當講究，用色數量越多，看起來越五花八門，面向的使用族群也越多。為了讓使用者有 貼切感 (服務的專一性)，通常用色不大於三種。
Adaptivity 提供系統自動調整變化，最好提醒使用者可以切換回去舊的介面設計，否則多個使用者在現實中交談時，可能會發生矛盾的錯亂交流。
Adaptability 提供使用者自定義，這些功能從系統中抽離出來，對於開發者來說是件好事，讓所有功能盡可能地讓特定使用者使用，但普遍性來說，大多數的功能都會被忽略，甚至當作從來沒有過。
Adaptability 類型的網頁設計，提供高度穩定性、客製化，有利於長時間的網站經營，培養長遠的顧客為主，對於短期入門的新手而言，對於客製化的吃力程度不一，當尚未熟悉系統前，對於功能設定處於一知半解狀態，需要閱讀文檔或累積經驗。因此在使用前期效率並不高，有待一段時間後，使用效率就有機會突破 Adaptivity 類型的。
正因為使用時間的長短，Adaptability 比較適合高頻率使用的軟體，而且功能性很強。相較於 Adaptivity 給予功能性較低，但操作起來會比較耗時 (滑鼠移動、滾動) 的軟體。
Evaluation of a personalized digital library based on cognitive styles: Adaptivity vs. adaptability
課程需求才看得，雖然我對裡面的實驗方法一點也不認同，很多地方沒有考慮進去，實驗的順序性有考慮到，卻沒有去考慮適應面向的主體，拿幾次任務的時間來進行比較往往是不夠的，根據時間成長的效率比較也應該被提出。
由於明天的課程有多數同學因畢業旅行而無法前來上課，因此明天上課的方式將不在課堂上進行，而改為同學閱讀所附的 paper，並找時間與組員討論所附的問題
請容許我罵一聲！我擦！為什麼不上課！雖然老師上課的認知風格與我不同，無法好好地學習知識，在盡可能地去適應，卻不斷地減少上課次數，學期結束前都還沒有適應吧。
曾想過明明有資源，卻怎麼樣都學不好嗎？在一個群體中學習，偏偏是落單的那一個人嗎？最近上課講到認知風格的相關內容，又對學習上有所障礙，到底是哪裡出了問題？
如果一名學生的認知風格與教師類似，這個學生就會有更積極的學習經歷，學習將會改善。
隊員如果擁有 類似認知風格 ，將會使他們對於參與有更 積極 的感受。而認知風格的匹配將使參與者與人共事時感覺更為 舒適 ，雖然它並不能獨自保證取得勝利的結果。
明明身處同一個環境下，成長幅度卻來得比別人低，沒錯！學習上完全沒有共鳴，導致學起來相當痛苦，建造、聚集知識的方式不同，兩路不相逢，要如何引領另一個走向相同目標？
在思考知識、經驗傳播問題前，先來認識自己，當然以前人所提供的分類方法，既不是唯一也不能二值劃分，必然有人有於兩邊優缺點，呈現自然分布，很少人是相當極端的特例！
接下來要胡言亂語囉！不用擔心！只是學習的過程不同，不代表能力的侷限。
看待一個事物時，採用策略的認知方法 (從舊有事物著手，了解處理事物之間的關聯)。來看看是怎麼 吸收 、 管理 新訊息。
美國心理學家威特金 (Witkin) 在 1940 年代研究垂直知覺時首先發現的。強調認知的過程而非內容。
場獨立自主、改造能力高，對於社會技能低。相反地，場依賴則在社會技能高，對於自主、改造能力低。當然從成長過程、性別差異，會逐漸地特化、轉變成另一類，並非完全由天生決定。
一種宅宅的既視感，不外乎差別就是願不願意聽外界，當個固執的聰明人還是頑固的蠢蛋，靠著外界成長就能成為現充，當個活在社會的人。場獨立則相當危險似的，若不是聰明的那一群，很容易被誤解、淘汰於社會中。 社會究竟是何物呢？
赫爾茲曼 (K.Holzman) 和克萊因 (Klein, 1954) 使用 水平 - 尖銳 認知型來描述認知風格的另一維度。
接下來分析行為上，有一種傾向。Leveller 運行 self-inwardness 模式，避免主動參與活動，對於指導、相助有迫切的需要，傾向於 自我貶抑 的性格。Sharpener 運行 self-outwardness 模式，相較於 Leveller 更喜歡 競爭 、 自我展現 ，對於成就有高度的需求，常常會逼迫自己推進。
看起來，Leveller 只是因為有 Sharpener 的人存在，才會偏向自我貶抑吧！而 Sharpener 擺明就是一個抖 M 推進器。
由卡根 (J.Kagan, 1964) 及同事提出來的，指在不確定條件下個體作出決定速度上的差異。
這兩種在整體性的工作上沒有任何差異，但反思型學習速度比較慢。
由吉爾福特 (Guilford, 1967) 在介紹智力模型時提出的。
只有一種答案不是很無趣嗎？對於我而言，越是要求那麼唯一，就越不是答案，也許是因為找不到唯一的答案吧，才去接受多種選項的可能性。
由帕斯克 (G.Pask, 1972) 和司科特 (Scott) 提出的。
序列導向的人肯定對於讀書這類的序列資料很感興趣，也比較能一頁一頁的讀完，對於整體導向的人而言，常常會跳躍章節去讀，才會逐漸深入理解。
序列導向通常面臨的是細節著重，而無法看到整體概念，整體導向則由整體概念來理解，而缺少細節的驗證。從具有遠見的程度來看，整體導向會比序列導向來得高，正因為不清楚，才有廣闊的視野吧！
心理學家 Paivio (1974) 提出了長時記憶信息如何被加工存儲的理論。影像儲存還是文字儲存？有一種原始影像資料和壓縮過後的大綱儲存差別，語言系統一改，壓縮而成的文字內容會造成理解錯誤吧？
Riding 和 Taylor 最初提出的。
根據許多研究，當學習材料不匹配時，得到的成績往往不理想。而在人格性質上，往往言語型偏向外向、形象型偏向內向。等等，好像明白為什麼語言類型的科目會比較難學，因為很難形象化，導致只有言語型的人可以在這一方面學習得不錯。
接續上一篇，接下來會有很多數學，自己也是一知無解狀態。
QEM 方程如下，當找到許多在等值曲面上的 $p_k$ 時，接著要找到一個最小 $v$ 參數為滿足目標方程
$v^{M} \leftarrow \text{arg } \underset{v}{min} \sum_{k} (n^t_{k} (v - p_{k}))^2$為了找到這個 $v$
$v^M \leftarrow v^M + Q^+ (q - Q v^M)$其中矩陣$Q = \sum_{k} n_{k} n^{t}_{k}$，
使用 SVD ( singular value decomposition )，奇異值分解去找解，這個計算好像在巨量資料中也存在 SVD，這世界太可怕了！ )。 在找到 $v^M$ 之後，進行簡化模型的縮點 (減少節點數)。經由這一步，可以更貼近物體的輪廓線，來強化邊緣的存在。
為了減少退化三角形跟三角網格的品質，可以藉由 Delaunay Tetrahedralization 再刷新一次。修改、刪除的點其實並不多於全局 (大多都是邊緣？)，那麼可以利用鬆弛的方式進行更新會比全局刷新還來得快速。
接下來這篇論文的作者，要進行實戰比較 (一起來吸收別人怎麼去驗證、統計、比較！實驗方法也是相當重要的。)，查看每一次迭代的是否可以的過程、速度。
利用模擬的模型 (幾何模型構成，拿真物要找到物體表面的方向量有點麻煩)，來看梯度方向的準確性，簡單來說就是拿實際結果與實驗結果中的一個點，於表面上的法向量夾角作為誤差大小。
$\varepsilon_{n}(p) = \text{arccos } (n(p)^t m(p))$即使是誤差，平滑也是好事。梯度越小越平滑。
接著它拿兩個物體 sphere 和 fandisk mesh (球體和一個 ???) 進行測試，看來在那些特殊的地方的誤差。算法可能會在某些特殊邊緣、平面的運行效果不好 (算法擅長於那些特徵計算、不善長什麼，來釐清這一點)。
視覺化時，利用下列二種方式凸顯梯度 central differences、Sobel operator (索貝爾運算就是在影像處理運用中，檢測邊緣、圖像梯度用的)。論文作者接下來提供一的新穎 CT value 的計算公式，與一般傳統的不同，讓這個誤差梯度下降。經由上面兩種方式的梯度表示，發現論文作者提供的這種會再更好一點點。
拿其他的建造方案，如 Grid-Based Polygonization，進行邊緣銳利比較。使用 Hausdorff distance 比較好壞，當然地 Grid-Based 沒對齊好，基本上贏不過三角化的版本！Grid-Based 取樣點夠密集才能勝過 vary triangle 的建模吧！在大多共平面的狀況下，三角形建模的方式需要頂點數非常少。
由於精準度上的調校，提出的方法比起常規的建模是消耗更多時間，但 CT 掃描數據的時間通常需要 10min 到 1hr，但是提出的方法比掃描時間還快。
也就是說讀取資料很慢，處理速度不用這麼快也沒關係，算起來有種 $O(n)$ 的效能。
由於過程中需要大量的矩陣、附加值於記憶體中，會消耗上 GB 的使用空間來維護操作。但現代電腦的記憶體可以超過 10GB 以上，因此這個缺點可以忽略不計。
為了加速運行，特別將物體表面周圍的取樣多、密集一點，對於其他地方的取樣少點，如此一來計算量會少很多。
在 $Tiso= (f(gi)+f(gj))/2$ 中提到插值法，但插值法有很多種，如 tricubic interpolation、bicubic interpolation … 等，如果選擇別種的插植法，效果會不會比較好呢？經過它們的梯度估算方法，他們所提到的插值法會稍微好一些。
提出一個可以用 CT 圖去建模的方法，仰賴的不是三維空間 volumetric data，並且可以提供一個更高精度的建模方法，用少許的三角形就能構造出相當銳利的結果。
提出一個速度慢、空間多的算法，但是現代電腦記憶體夠，速度慢沒關係，比輸入還快就行了
先來上競賽中最常見到的快速冪次寫法
|
|
這樣的寫法，只運算 64-bits 內的結果相當不錯，與接下來講的算法速度差異並不大。但對於近代加密所需要的離散對數過程，則會有放大速度差異，因為 x, y, mod 三個參數的 bit-length 都相當長。
做法就是最普遍見到的。
|
|
|
|
|
|
|
|
也就是說，每一次迭代，將會將指數左移 (R = R ^ 2 就是要移動 R^xxxx 變成 R^xxxx0，切著看是否要乘上 x 來變成 R^xxxx1)，這方法雖然不錯，但是計算高位元空迴圈可是不能忽略！當然對於設計電路的人，固定變量的迴圈展開後就不存在這問題。
效能上，期望的乘法次數與 Right-To-Left 是差不多的！長度為 n bits 的數字，期望值會有 $n/2$ 個 1，因此大約需要 $n/2$ 次乘法。
|
|
|
|
長度為 n bits 的數字，倆倆一起期望值會有 $3n/8$ 個非 0 (00, 01, 10, 11 中 4 個有 3 個 $!= 0$，計算組數只有 $n/2$)，因此大約需要 $3n/8$ 次乘法。比剛剛快上一點呢 ( $3n/8 < n/2$ )！
|
|
|
|
期望的乘法次數 $n/3$，這很可怕，別問我！
| Algorithm Name | Table Size | #squaring | Average #Multiplication |
|---|---|---|---|
| Right-To-Left | 1: $x^{2^i}$ | $n$ | $n/2$ |
| Left-To-Right | 1: $x$ | $n$ | $n/2$ |
| Left-To-Right(2-bits) | 3: $x$, $x^2$, $x^3$ | $n$ | $3n/8$ |
| Left-To-Right(sliding) | 2: $x$, $x^3$ | $n$ | $n/3$ |
上述四種方法中，不外乎都存在 Conditional Jump 出現，會導致執行速度跟程式計數器 (Program Counter) 移動上會有所差別。可以進行實作攻擊，從分析時間、電源不穩攻擊，來找到 $a$ 究竟是何物 (通常要偷的都是 $x^a$ 上面的 $a$)！電源雜訊干擾於當指令執行到 Conditional Jump 時，干擾 $R$ 的計算發生錯誤，如果沒有發生錯誤，表示 $a \left [ i \right ] = 0$，反之就能知道 $a \left [ i \right ] = 1$。
很趣味地是提供一個不需要 Conditional Jump 的寫法 (實作上)，一樣會有這種問題！
|
|
提供一個不相干的垃圾暫存器 (redundancy register) 來減少 Jump 的問題，很明顯地 電源雜訊干擾 的攻擊仍然存在！這作法很有趣的啊！只是會被攻擊。
|
|
這作法避開之前的問題，解決其中一種被攻擊的方案。
過程中都滿足 $R \left [ 0 \right ] = R \left [ 1 \right ] \times g$，同時 $R \left [ 0 \right ]$ 會是最後的答案。
|
|
明顯地，$R \left [ 1 \right ]$ 的計算是為了下一次為 $a \left [ i+1 \right ] = 1$ 而存在的！
筆記錯誤多多，請以僅供參考的角度去質疑
Please compare the CFB mode the OFB mode by providing a table indicating at least 5 of their advantage and corresponding disadvantage.
This question is about issues of random access of encryption and decryption. Define notations or symbols you need before providing your answer. Please describe how to use CFB mode and CTR mode to randomly encrypt and decrypt a file Why OFB mode is inappropriate to randomly encrypt and decrypt a file?
What is the one-time pad (please provide a figure to explain it) and what is the main security requirement ?
Follow
Follow
What is the avalanche effect of a block cipher ?
What is the Triple -DES with two keys ? Please explain the process the derive the complexity of meet-in-the-middle attack on Triple-DES with two keys.
For all AES round operations, which operation(s) provides substitution and which operations(s) provides diffusion ?
Please describe the details of BBS pseudorandom number generator.
Below is the pseduo code of RC4. Please design a modified RC4 version with message dependent property of key stream.
|
|
請參照 《資訊安全 小考筆記》
請參照 《資訊安全 小考筆記》
one-time pad 概念圖如下
|
|
one-time pad 主要是靠 key 不重複使用來維護資料安全，但是雙方同時產生出相同的 random key 是很困難。由於不重複使用，靠一個 random key 的產生提供 random mask 消除明文和祕聞之間的關係。但是雙方都要相同 random key 是相當困難的，通常 generator 是由某個偽隨機數產生器，由演算法產生的到底是不是隨機數呢？
一定要 random key，不能有任何的 dependent、 不能重複 (reuse) ，否則會有 已知明文攻擊 。
ECB mode 在相同明文對應相同的密文，這容易受到大多數的攻擊，如收集已知明文或密文所進行的攻擊。由於明文和密文的關係明確，也因此在 圖片資料 加密傳送，會出現 大量重複 的密文。
CBC mode 提供 random mask 的效果
$$C_{-1} = IV \\ C_{i} = E_{k}(C_{i-1} \text{ XOR } P_{i}) \\$$從$C_{i-1} \text{ XOR } P_{i}$ 操作中可以發現到，讓相同的明文對應到不同的密文 (在前一個密文不同時)，解決 ECB 在相同明文加密只會對應種密文。
Shannon’s idea 請參照 《資訊安全 小考筆記》
Feistel cipher structure 藉由三個規則實作
Avalanche effect 讓相似的明文 Pi, Pj (漢明距離 $H(Pi, Pj) = 1$ … 之類的) 對應的密文 Ci, Cj 能有相當大的差異 (漢明距離 $H(Ci, Cj) = \text{half-bit}$ 的期望值)，將只有一點不同的差異，擴散到密文的每個地方，放大差異的效果。
Triple-DES
$E_{k_{1}}\left [ D_{k_{2}} \left [ E_{k_{1}} \left [ P_{i} \right ] \right ] \right ] = C_{i}$當指使用兩次的 DES，受到中間相遇法的攻擊，理論上的複雜度與 1 個 DES 一樣，複雜度大約都在 $O(2^{56})$，因此效果並沒有變得更好。然而在 Triple-DES 複雜度就提升到 $O(2^{112})$。
從已知的明文、密文，目標是讓 $X = Y$，窮舉 key，如果發生 $X = Y$ 則表示找到一組可行的解。窮舉得到 $X$ 的複雜度為 $O(2^{56} \times 2^{56}) = O(2^{112})$，而 $Y$ 則需要 $O(2^{56})$，當 $X = Y$ 符合時，則表示 key 找到！
當然也可以抽換相遇的地點，如下是另外一種
$$X = E_{k_{1}} \left [ P_{i} \right ] \\ C_{i} = E_{k_{1}} \left [ D_{k_{2}} \left [ Y \right ] \right ]$$不管怎麼切割，都至少要窮舉兩把 key 來得到其中一個相遇結果，複雜度都落在 $O(2^{112})$。如果說對應兩個表的結果需要 $O(log \text{ n})$ 的時間，則複雜度為 $O(112 \times 2^{112})$。
| Step | Function |
|---|---|
| Substition Bytes | substitution |
| Shift Rows | diffusion |
| Mix Column | diffusion, substitution |
| Add Round Key | substitution |
比較討厭的是 Shift Rows 為什麼提供是 diffusion，明明對於兩個相似明文加密上，漢明距離沒有增加！但是 diffusion 不只是讓差異數量增加，還要考量差異位置的變動，相鄰差異的位置被轉移到兩個遠處，就能提供 diffusion！這會讓攻擊者無從判定差異的對應。
message dependent RC4
第一版本
|
|
好像不管怎麼寫兩邊似乎都很難相同。
第二版本
|
|
感覺上述的寫法，萬一 C 被竄改，會導致錯誤擴散，而且是全部失效，這讓我非常納悶。
這次要挑戰的題目為 UVa 12647 - Balloon，由於網路上有一些線段樹的作法，如
http://www.cnblogs.com/yours1103/p/3426212.html
這裡可以看到有一些人利用線段樹來完成操作，實際上的做法根據掃描線，y 座標從高度低到高、或者是高到低的線段依序放入，到時候查找第一個獲最後一個覆蓋的線段編號。
UVa 12647 - Balloon 主要是在問，給予一些天花板，請問放置一個氣球，氣球會沿著天花板歪斜的地方移動 (如果沒歪則停止)，詢問最後停留的位置。有可能會飛到無窮遠，則輸出最後的 x 座標，反之輸出停留的 (x, y) 地點。如果發生一個地點有數個天花板，發生擦邊情況，則氣球會依據第一個碰觸到的天花板進行移動。
既然發現它們 (搜尋可以找到至少兩個大大的線段樹寫法) 基本上都是按照覆蓋的方式，找到覆蓋編號去完成移動、建造飛行的所有可能。
明顯地，由於天花板線段的斜率有正有負，不能保證根據 y 座標排序可以決定飛行到下一個的高度的 x 範圍。因此交錯 y 座標線段，讓覆蓋方案失效。
下面有數組測資，可以讓史蒂芙掉測資、也會讓網址中的代碼掉。史蒂芙認為覆蓋不好，那用最大最小值去維護如何！這樣也許就好點了吧？但不幸地，這麼做一樣會遇到排序 y 的問題，不管怎麼排序，都會造成建構方法不正確。
challenge 的題目還不太會傳，中間有點小問題。
|
|
排列 1 到 n 的整數，使得相鄰兩數互質，部分位置一定要填入某些數字，請問剩餘數字的填法方案數為何？
|
|
|
|
bitmask 下去 dp[N][1<<N][N]，dp[i][j][k] 表示前 i 個位置，已經使用的數字狀態 j，最後一個數字 k。不曉得需不需要滾動，記憶體用量驚人。萬萬沒想到，撰寫過程中坑了一個建表的 gcd[20][20]，當 n = 20 時，直接 index out of bound，先撇開這個蠢錯。滾動數組下去玩，真是誘人的時間限制，再次得到 9.990s TLE 的事蹟 ！仔細想想，運算過程中只出現加法，將 mod 運算替換成條件判斷 + 減法，
|
|
2015 Google Code Jam Round 1A 中，C - Logging 有點嚴重的問題！很多精準度不高的代碼都通過了！現在要求去找到測資 tricky cases，讓他們通通 WA！
原題是對於任意平面點，找到要移除最小的平面點，使得自己在凸包邊緣上。標準的極角排序，維護 180 度以內 (半平面) 的點個數。
atan2
esp = 1e-12not enough for $x, y \in \left [0, 10^6 \right]$，極角排序替代方案！快來戳我的講法，看 POJ 類似的題目，精準度要壓到 1e-16 呢，所以誤差還要抓更小才行。
等等，challenge 這一題時，自己的代碼也 WA 了！
一開始誤以為是 index out of bound，assert() 下去都沒發生。後來估計是 atan2(y, x) 的誤差，對此誤差早有耳聞，解題撞壁的機會很低。咱很蠢，隨機生了 1000 萬個平面點，按照 atan2 排序，檢查相鄰兩個座標的外積 (叉積) 是否為逆時針，跑一次隨機生成大概能爆出一個誤差的相鄰點，十來次得到 n 個點，隨機組合這 n 個點於四個象限，再亂撒少數個點，再跟自己撰寫的代碼做比對 (中間又測了上萬組)。
|
|
|
|
利用外積的計算方案，誤差情況會更小。又因為是整數座標，基本上是不產誤差。
|
|
生了 10000 組，終於在裡面發現其中幾組。
|
|