課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-05-11截止時間：2021-05-18 題目說明這次的作業是 UVa 中的 2 題題目，與 Closest Pair Problem 有關。 UVa 10245 - The Closest Pair Problem：UVa - 10245 解題紀錄 UVa 11378 - Bey Battle：UVa - 11378 解題紀錄

題目： UVa - 11378 - Bey Battle 題目說明 給你點的位置，求出以各個點為中心的正方形，邊長最多可達多少？每個正方形邊長須一樣，可剛好接觸到。 UVa 11378 - Bey Battle | NaiveRed’s Blog 解題思路Closet Pair Problem，可用 Divide and Conquer。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include <bits/stdc++.h>using namespace std;#define FOR(i, a, b) for (int i = a; i < b; ++i)#define CLR(c) memset(c, 0, sizeof(c))static auto __ = []{ ...

題目： UVa - 10245 - The Closest Pair Problem 題目說明給一些在二維平面上的點，求最近的兩點距離為何。 Input： 每組測資第一個整數 N，表示有幾個點 ( 若 N 為 0 表結束 )，後面 N 行每行有兩個整數，表點的座標。 Output： 輸出最近的兩點距離為何，輸出至小數點後四位，若超過 10000 則輸出 "INFINITY"。 解題思路Closet Pair Problem，可用 Sweep line 或 Divide and Conquer。 參考解法Sweep line: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include <bits/stdc++.h>using namespace std;#define FOR(i, a, b) for (int i = a; i < b; ++i)#defin ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-05-11截止時間：2021-05-18 題目說明這次的作業是 UVa 中的 3 題題目，與 Convex Hull 有關。 UVa 681 - Convex Hull Finding：UVa - 681 解題紀錄 UVa 1206 - Boundary Points：UVa - 1206 解題紀錄 UVa 11096 - Nails：UVa - 11096 解題紀錄

題目： UVa - 11096 - Nails 題目說明給一些在二維平面的座標點，求包住所有座標點的最小多邊形的周長。 Input： 第一個整數 T，表示有 T 組測資，每組測資的前兩個整數分別代表 l、N，後面 N 行每行有兩個整數表示座標點。 Output： 輸出包住所有座標點的最小多邊形的周長，若小於 l 則輸出 l。 解題思路此解法需要有 Convex Hull 及 Graham Scan 演算法的概念 簡單的凸包題，使用 Graham Scan 演算法找出所有頂點，之後計算周長即可。需要注意的是，若 n 為二，則周長為兩點距離乘二。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105#include <b ...

題目： UVa - 1206 - Boundary Points 題目說明給一些在二維平面的座標點，求包住所有座標點的最小多邊形的頂點座標。 Input： 每行為一組測資，每組括號為一個座標點。 Output： 依照 Input 的格式輸出那些點的座標，起點在最後必須再輸出一次。 解題思路此解法需要有 Convex Hull 及 Graham Scan 演算法的概念 簡單的凸包題，使用 Graham Scan 演算法找出所有頂點即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include <bits/stdc++.h>using namespace std;#define FOR(i, a, b) for (int i = ...

題目： UVa - 681 - Convex Hull Finding 題目說明給一些在二維平面的座標點，求包住所有座標點的最小多邊形的頂點座標。 Input： 第一個整數 T，表示有 T 組測資，每組測資第一個整數 N，表示有 N 個點，後面 N 行，每行有兩個整數，表示座標點。每組測資中間以 -1 隔開。 Output： 先輸出 T，之後每組測資先輸出最小多邊形的頂點個數，之後逆時針輸出那些點的座標，起點在最後必須再輸出一次。每組測資中間以 -1 隔開。 解題思路此解法需要有 Convex Hull 及 Graham Scan 演算法的概念 簡單的凸包題，使用 Graham Scan 演算法找出所有頂點即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697 ...

課程名稱：演算法概論 CS309 B授課教師：林基成發放時間：2021-05-03截止時間：2021-05-10 題目說明這次的作業是 UVa 中的 4 題題目，與 Maximum Flow 有關。 UVa 10330 - Power Transmission：UVa - 10330 解題紀錄 UVa 11380 - Down Went The Titanic：UVa - 11380 解題紀錄 UVa 11506 - Angry Programmer：UVa - 11506 解題紀錄 UVa 12125 - March of the Penguins：UVa - 12125 解題紀錄

題目： UVa - 12125 - March of the Penguins 題目說明 給定一些冰塊，每個冰塊上有一些企鵝，每個冰塊有一個可以跳出的次數限制，每個冰塊位於一個坐標，現在每個企鵝跳躍力為d，問所有企鵝能否跳到一點上，如果可以輸出所有落腳冰塊，如果沒有方案就打印 -1。 UVA 12125 - March of the Penguins（最大流）_Remilia’s-CSDN博客 解題思路最大流，依照上面的說明建邊後使用 Dinic 求解即可。 參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312 ...

題目： UVa - 11506 - Angry Programmer 題目說明 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線，希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費，問需要的最小總花費多少。 UVA 11506 - Angry Programmer ( Mincut, Flow ) - 0w1 解題思路最大流，依照上面的說明建邊後使用 Dinic 求解即可。 參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110#include <bits/stdc++.h>using namespace std;#define FOR(i, a, ...