題目: UVa - 681 - Convex Hull Finding
題目說明
給一些在二維平面的座標點,求包住所有座標點的最小多邊形的頂點座標。
Input: 第一個整數 T
,表示有 T
組測資,每組測資第一個整數 N
,表示有 N
個點,後面 N
行,每行有兩個整數,表示座標點。每組測資中間以 -1 隔開。
Output: 先輸出 T
,之後每組測資先輸出最小多邊形的頂點個數,之後逆時針輸出那些點的座標,起點在最後必須再輸出一次。每組測資中間以 -1 隔開。
解題思路
此解法需要有 Convex Hull 及 Graham Scan 演算法的概念
簡單的凸包題,使用 Graham Scan 演算法找出所有頂點即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
| #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 __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
const int INF = (int)1e9; const int MXN = 600;
struct Point { int x; int y; double d; };
Point P[MXN];
int T; int N; int top;
double dist(const Point& l, const Point& r) { return sqrt(pow(l.x - r.x, 2) + pow(l.y - r.y, 2)); }
int crossProduct(const Point& o, const Point& a, const Point& b) { return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y); }
bool cmp1(const Point& l, const Point& r) { return l.y == r.y ? l.x < r.x : l.y < r.y; }
bool cmp2(const Point& l, const Point& r) { auto cp = crossProduct(P[0], l, r); return cp == 0 ? l.d < r.d : cp > 0; }
void read() { static int tmp; cin >> N; FOR(i, 0, N) cin >> P[i].x >> P[i].y; if (T) cin >> tmp; }
void GrahamScan() { sort(P, P + N, cmp1); FOR(i, 1, N) P[i].d = dist(P[0], P[i]); sort(P + 1, P + N, cmp2);
top = 1; P[N++] = P[0]; FOR(i, 2, N) { while (top > 0 && crossProduct(P[top - 1], P[top], P[i]) <= 0) --top; P[++top] = P[i]; } }
void solve() { if (top < 2) { cout << "0\n"; return; }
cout << top + 1 << '\n'; FOR(i, 0, top + 1) cout << P[i].x << ' ' << P[i].y << '\n'; if (T) cout << "-1\n"; }
int main() { cin >> T; cout << T << '\n'; while (T--) { read(); GrahamScan(); solve(); } }
|
參考資料
UVa 681 - Convex Hull Finding_小白菜又菜-CSDN博客