首頁 Uva Problems

# 題目: 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