• itertool.combinations(points, 一次產生3組) 可以窮舉

• for (a,b),(c,d),(e,f) in combination(): 可以在for指定參數的地方就把point解開來

  把公式抄下來，用abs()取代絕對值| |

• f'{m:.2f}' 精度就會二
  
  
  

• points在生成的時候，可以用itertools.islice(stdin, N組)，寫成list comprehension的樣子

窮舉的速度是1.5s

不知道其他大佬是使用什麼辦法加速的 ˊ ˋ

這題可以先求出凸包（Convex Hull）——即座標平面上包覆著給定的 N 個點之最小多邊形。而這可以藉由 Andrew's Monotone Chain Convex Hull Algorithm 在 O(n log n) 時間內求出。

接著就按照原本的暴力方式窮舉凸包上的點。對於隨機生成點的測資基本上就會快很多，即 O(h ^ 3)，其中 h 為凸包上的點個數。

當然，精心設計的測資依舊可以讓你退化回 O(N ^ 3)。

據說可以利用旋轉卡尺（Rotating Calipers）最佳化搜尋方式，不過因為我自己沒實作過所以無法講解。不過對於本題來說，凸包就已經很夠用了。

以上。希望有幫助到您。

2018 年時的 server 比較快  

這題可以先求出凸包（Convex Hull）——即座標平面上包覆著給定的 N 個點之最小多邊形。而這可以藉由 Andrew's Monotone Chain Convex Hull Algorithm 在 O(n log n) 時間內求出。

 

接著就按照原本的暴力方式窮舉凸包上的點。對於隨機生成點的測資基本上就會快很多，即 O(h ^ 3)，其中 h 為凸包上的點個數。

 

當然，精心設計的測資依舊可以讓你退化回 O(N ^ 3)。

 

據說可以利用旋轉卡尺（Rotating Calipers）最佳化搜尋方式，不過因為我自己沒實作過所以無法講解。不過對於本題來說，凸包就已經很夠用了。

 

以上。希望有幫助到您。

 

 

這個凸包好像有在其他題看過，感覺很難就跳過了XD  旋轉卡尺也是，哈！

這些演算法通常是算在什麼範疇內呢？圖論嗎？是不是跟cluster(聚類分析)有點像呀？Machine Learning K-means那些的

不知道您在哪裡學習到這些知識的呢？有什麼推薦的解說嗎？「演算法筆記」的寫法有點太簡潔了哈

https://web.ntnu.edu.tw/~algo/ConvexHull.html

2018 年時的 server 比較快  

 

了解，有時候我看一些簡單的題目排行榜會有8ms或是18ms，也是一樣的原因嗎？

d555

b859

單側的。

d555

b859

單側的。

［d555: 平面上的極大點］我先依x軸建dict分類、用set裝y，從x的最大往回推，取max(set)與y_max比較，但是記憶體用量沒有像你這麼省，是在建置資料的時候有什麼增強嗎？

我後來參考「演算法筆記」使用 「Convex Hull:Andrew's Monotone Chain凸包」的技巧，

程式碼比較簡潔了，但是並沒有加速，還變得更慢了！真有趣(建dict分類1.5s -> 直接跑for迴圈2.3s)

每個 key 留一個值就好。

每個 key 留一個值就好。

成功了！速度真的快了0.3s！但是記憶體用量依然還是很高，可能輸出的部分有什麼問題吧？

用字串直接相接 或是 用 list.append+reversed+stdout.writeline 記憶體降到20MB但速度就被拖慢了

這個凸包好像有在其他題看過，感覺很難就跳過了XD  旋轉卡尺也是，哈！

這些演算法通常是算在什麼範疇內呢？圖論嗎？是不是跟cluster(聚類分析)有點像呀？Machine Learning K-means那些的

不知道您在哪裡學習到這些知識的呢？有什麼推薦的解說嗎？「演算法筆記」的寫法有點太簡潔了哈

https://web.ntnu.edu.tw/~algo/ConvexHull.html

凸包和旋轉卡尺比較是屬於幾何學（Geometry）的範疇。而圖論（Graph Theory）比起幾何更接近像是「群論」（Group Theory）和「拓撲學」（Topology），主要研究的是物件與物件之間的「關係」。

當然，這不代表著圖論跟幾何學毫無關係。

至於凸包我已經不記得是什麼時候首次遇到的。總之如果單一來源（例如演算法筆記）看不懂就看更多的資訊 & 來源。例如以下是 Wikibooks 關於 Andrew's Monotone Chain Convex Hull Algorithm 的動畫圖例：

可以看到 GIF 的前半部分是在求「上半」的凸包，後半則是「下半」。

而我自己的理解是：

該演算法的精神是先將所有點按照 X 軸小到大排序，再按照 Y 軸由小到大排序。這樣子第一個點將會是最「左下」的點。而且可以看到最「左下」的點必定在凸包裡，因此一開始先將其加入凸包中。

接著想像一條隱形的掃描線從最左側的點掃到最右側，之後每次碰到一個新的點 X 就預先與凸包最後加入的那一個點 Y 連線看看。此時如果凸包中有倒數第二加入的點 Z，則我們可以利用外積（Cross Product）來判斷邊 XY 跟邊 YZ 是呈順時針方向還是逆時針方向。

如果邊 YZ 相對於邊 XY 是呈現順時針方向（甚至是 X 、 Y 、 Z 共線），則代表 Y 這個點將會處於邊 ZX 的「內部」。也就代表著 Y 不應為凸包的一個頂點，因此將其移除；反之如果方向是逆時針則沒事。

示意圖如下：

因此掃到最右側之後便可以得出上半部的凸包。而下半部只要從最右側掃回到最左側，然後仿照原本上半的作法即可。

以上。希望可以幫助您理解凸包。

凸包和旋轉卡尺比較是屬於幾何學（Geometry）的範疇。而圖論（Graph Theory）比起幾何更接近像是「群論」（Group Theory）和「拓撲學」（Topology），主要研究的是物件與物件之間的「關係」。

當然，這不代表著圖論跟幾何學毫無關係。

.....

..... (恕刪)

以上。希望可以幫助您理解凸包。

感謝您耐心解說！原來是跟幾何學比較有關係

我一開始看「演算法筆記」只有看到上半部，後來看到 Andrew’s Monotone Chain 才發現原來這個演算法這麼炫 XD

仔細研究後發現真的蠻有趣的！

但是「確認同cross product方向一致」，是「要確認每個在stack的點，方向完全都一致後」才會進行下一輪

這樣為什麼還是O(N)呢？

1.     // 包下半部
2.     for (int i=0; i<10; ++i)
3.     {
4.         while (m >= 2 && cross(CH[m-2], CH[m-1], P[i]) <= 0) m--;
5.         CH[m++] = P[i];
6.     }

第4.行，刪除方向不同的點 的while迴圈 ， 這樣會比N多一點點(我也不確定多了多少)

 

感謝您耐心解說！原來是跟幾何學比較有關係

我一開始看「演算法筆記」只有看到上半部，後來看到 Andrew’s Monotone Chain 才發現原來這個演算法這麼炫 XD

仔細研究後發現真的蠻有趣的！

但是「確認同cross product方向一致」，是「要確認每個在stack的點，方向完全都一致後」才會進行下一輪

這樣為什麼還是O(N)呢？

 

1.     // 包下半部
2.     for (int i=0; i<10; ++i)
3.     {
4.         while (m >= 2 && cross(CH[m-2], CH[m-1], P[i]) <= 0) m--;
5.         CH[m++] = P[i];
6.     }

 

第4.行，刪除方向不同的點 的while迴圈 ， 這樣會比N多一點點(我也不確定多了多少)

簡單來說，我們只會掃過每個點一次且僅有一次。而每個點都會進入到堆疊中（過程中的凸包之變化與堆疊相同，都符合先入先出（First In First Out）），並有可能在之後的某個時刻被移出堆疊。

那麼以總體來說，每個點最多進去一次、出去一次，總共被「摸」到兩次（這邊先忽略外積的部分）。因此整體的（即程式碼的 for 包 while 之部分）時間複雜度為 O(2N) = O(N)。也因此中間的 while 迴圈之操作平攤（Amortized）後可視為 O(1)。

而這種概念被稱為平攤分析（Amortized Analysis），經常用來計算和分析資料結構的操作時間複雜度。有興趣的話，可以先去維基過目一下同名的條目——平攤分析。

 

感謝您耐心解說！原來是跟幾何學比較有關係

我一開始看「演算法筆記」只有看到上半部，後來看到 Andrew’s Monotone Chain 才發現原來這個演算法這麼炫 XD

仔細研究後發現真的蠻有趣的！

但是「確認同cross product方向一致」，是「要確認每個在stack的點，方向完全都一致後」才會進行下一輪

這樣為什麼還是O(N)呢？

 

1.     // 包下半部
2.     for (int i=0; i<10; ++i)
3.     {
4.         while (m >= 2 && cross(CH[m-2], CH[m-1], P[i]) <= 0) m--;
5.         CH[m++] = P[i];
6.     }

 

第4.行，刪除方向不同的點 的while迴圈 ， 這樣會比N多一點點(我也不確定多了多少)

簡單來說，我們只會掃過每個點一次且僅有一次。而每個點都會進入到堆疊中（過程中的凸包之變化與堆疊相同，都符合先入先出（First In First Out）），並有可能在之後的某個時刻被移出堆疊。

 

那麼以總體來說，每個點最多進去一次、出去一次，總共被「摸」到兩次（這邊先忽略外積的部分）。因此整體的（即程式碼的 for 包 while 之部分）時間複雜度為 O(2N) = O(N)。也因此中間的 while 迴圈之操作平攤（Amortized）後可視為 O(1)。

 

而這種概念被稱為平攤分析（Amortized Analysis），經常用來計算和分析資料結構的操作時間複雜度。有興趣的話，可以先去維基過目一下同名的條目——平攤分析。

原來如此，最多摸到兩次！

之前有看過［動態陣列的平攤分析］，是O(1)，之前也是不了解開空間複製要O(n)怎麼會O(1)，看到平攤分析才知道是平均下來O(1)

沒想到這裡又用上了一樣的概念，沒有記在心裡(或者說，不知道可以用在這裡，也不會使用，哈)，謝謝你的解說，有了解了！