# 題目: UVa 681 - Convex Hull Finding
# 題目說明
給 N
個點 (x, y 平面座標),求這些點的 凸包(Convex Hull)
INPUT:
第一行輸入一個整數 T
,代表測資數
每筆測資輸入一個整數 N
,接下來有 N
行,每行輸入兩個點 (x, y)
,為點的座標
輸入一個 -1
間隔測資
OUTPUT:
與輸入幾乎相同
區別在於 N
改為凸包的 node
數量,即分別輸出 node
的座標
起點需輸出 2 次 (頭尾)
# 解題方法
能夠使用 Graham's Scan
演算法
或者 Andrew's Monotone Chain
演算法
Graham's Scan
需要做極角排序
Andrew's Monotone Chain
先找到起點 (最左下的點),按照順序尋找下一個點,直到終點,這會構成一半的凸包
再從終點開始反方向尋找,直到起點,最後會構成完整的凸包
# 參考程式碼 Graham's Scan
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <math.h> | |
using namespace std; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
struct point | |
{ | |
int x; | |
int y; | |
double d; | |
}; | |
vector< point > V; | |
vector< point > ret; | |
int T, N, a, b, _; | |
double dist(point& a, point& b) | |
{ | |
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2)); | |
} | |
double cross(point & o, point & a, point & b) | |
{ | |
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); | |
} | |
bool cmp(point& a, point& b) | |
{ | |
auto c = cross(V[0], a, b); | |
return c == 0 ? a.d < b.d : c > 0; | |
} | |
void read(int t) | |
{ | |
if (t) cin >> _; | |
cin >> N; | |
V.clear(); | |
for (int i = 0; i < N; ++i) cin >> a >> b, V.push_back({ a, b }); | |
} | |
void GrahamScan() | |
{ | |
sort(V.begin(), V.end(), [](point& a, point& b) | |
{ return a.y < b.y || (a.y == b.y && a.x < b.x); }); | |
for (int i = 1; i < N; ++i) V[i].d = dist(V[0], V[i]); | |
sort(V.begin() + 1, V.end(), cmp); | |
ret.clear(); | |
V.emplace_back(V[0]); | |
for (int i = 0; i <= N; ++i) | |
{ | |
int m = ret.size(); | |
while (m >= 2 && cross(ret[m - 2], ret[m - 1], V[i]) <= 0) | |
{ | |
ret.pop_back(); | |
--m; | |
} | |
ret.emplace_back(V[i]); | |
} | |
} | |
void print(int t) | |
{ | |
if (t) cout << "-1\n"; | |
cout << ret.size() << "\n"; | |
for (auto& [x, y, d] : ret) cout << x << " " << y << "\n"; | |
} | |
int main() | |
{ | |
cin >> T; | |
cout << T << "\n"; | |
for (int i = 0; i < T; ++i) | |
{ | |
read(i); | |
GrahamScan(); | |
print(i); | |
} | |
} |
# 參考程式碼 Andrew's Monotone Chain
#include <iostream> | |
#include <vector> | |
#include <algorithm> | |
#include <math.h> | |
using namespace std; | |
struct point | |
{ | |
int x; | |
int y; | |
}; | |
int T, N; | |
vector< point > V; | |
vector< point > ret; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
void init() | |
{ | |
V.clear(); | |
ret.clear(); | |
} | |
void read(int t) | |
{ | |
int a, b, _; | |
cin >> N; | |
for (int i = 0; i < N; ++i) cin >> a >> b, V.push_back({ a, b }); | |
if (t != T) cin >> _; | |
} | |
double cross(point& o, point& a, point& b) | |
{ | |
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); | |
} | |
void Andrews_Monotone_Chain() | |
{ | |
sort(V.begin(), V.end(), [](point& a, point& b) | |
{ return a.y < b.y || (a.y == b.y && a.x < b.x); }); | |
for (int i = 0; i < N; ++i) | |
{ | |
int m = ret.size(); | |
while (m >= 2 && cross(ret[m - 2], ret[m - 1], V[i]) <= 0) | |
{ | |
ret.pop_back(); | |
--m; | |
} | |
ret.emplace_back(V[i]); | |
} | |
for (int i = N - 2, t = ret.size() + 1; i >= 0; --i) | |
{ | |
int m = ret.size(); | |
while (m >= t && cross(ret[m - 2], ret[m - 1], V[i]) <= 0) | |
{ | |
ret.pop_back(); | |
--m; | |
} | |
ret.emplace_back(V[i]); | |
} | |
} | |
void print(int t) | |
{ | |
cout << ret.size() << "\n"; | |
for (auto& [x, y] : ret) cout << x << " " << y << "\n"; | |
if (t != T) cout << "-1\n"; | |
} | |
int main() | |
{ | |
cin >> T; | |
cout << T << "\n"; | |
for (int i = 1; i <= T; ++i) | |
{ | |
init(); | |
read(i); | |
Andrews_Monotone_Chain(); | |
print(i); | |
} | |
} |
# 參考資料
https://blog.rice9547.me/2019/05/10/uva-681-convex-hull-finding/
http://web.ntnu.edu.tw/~algo/ConvexHull.html
https://zh.wikipedia.org/wiki/%E5%87%B8%E5%8C%85