UVA 681 - Convex Hull Finding
Contents
本題為中山大學高等程式設計課程作業指定題目之三星題。
題目大意
給你 n 個點，從左下角開始，逆時鐘輸出最小且能包覆這 n 個點的圖形的每個頂點的座標。
輸入範圍
最大頂點數為 512，1 <= n <= 512 * 512。
解法
這題是很裸的凸包題。先依照座標進行排序，從最左下角的點開始，把凸包下半部的點找出來，再從下半部的終點往上走，最後會走回原點(因為是最左下的)。使用外積可以判斷點是否為凸包的頂點，在逆時鐘的情況下，若向量OA * 向量OB < 0，代表向量 OA 到向量 OB 是順時鐘，也就是 A 點是凹進去的，等於 0 則代表 A 點和 B 點重疊。
實作上我使用 vector，由於會存取很多次 size，且尋找點的時候有些 stack 的味道，使用 array 做應該會比較好。
有點奇怪的是，不知道為什麼 UVA 似乎只有 input 沒有 output，作答時可以去 udebug 做測試。
程式碼
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> Point;
double cross(Point o, Point a, Point b) {
return (a.first - o.first) * (b.second - o.second) - (a.second - o.second) * (b.first - o.first);
}
int main(int argc, char *argv[]) {
int T, n;
cin >> T;
cout << T << endl;
while(T--) {
cin >> n;
vector<Point>v(n);
for(int i=0; i<n; i++) {
cin >> v[i].first >> v[i].second;
}
sort(v.begin(), v.end(), [](Point a, Point b) {
return a.second < b.second || (a.second == b.second && a.first < b.first);
});
vector<Point>res;
for(int i=0; i<n; i++) {
int m = res.size();
while(m >= 2 && cross(res[m-2], res[m-1], v[i]) <= 0) {
res.pop_back();
m--;
}
res.push_back(v[i]);
}
for(int i=n-2, t=res.size()+1; i>=0; i--) {
int m = res.size();
while(m >= t && cross(res[m-2], res[m-1], v[i]) <= 0) {
res.pop_back();
m--;
}
res.push_back(v[i]);
}
cout << res.size() << endl;
for(int i=0; i<res.size(); i++) cout << res[i].first << " " << res[i].second << endl;
if (T) {
cin >> n;
cout << "-1\n";
}
}
return 0;
}