題目: UVa - 11096 - Nails
題目說明
給一些在二維平面的座標點,求包住所有座標點的最小多邊形的周長。
Input: 第一個整數 T
,表示有 T
組測資,每組測資的前兩個整數分別代表 l
、N
,後面 N
行每行有兩個整數表示座標點。
Output: 輸出包住所有座標點的最小多邊形的周長,若小於 l
則輸出 l
。
解題思路
此解法需要有 Convex Hull 及 Graham Scan 演算法的概念
簡單的凸包題,使用 Graham Scan 演算法找出所有頂點,之後計算周長即可。需要注意的是,若 n 為二,則周長為兩點距離乘二。
參考解法
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 104 105
| #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 = 102;
struct Point { double x; double y; double d; };
Point P[MXN];
int N; int top; double l;
double dist(const Point& l, const Point& r) { return sqrt(pow(l.x - r.x, 2) + pow(l.y - r.y, 2)); }
double 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() { cin >> l >> N; FOR(i, 0, N) cin >> P[i].x >> P[i].y; }
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; FOR(i, 2, N) { while (top > 0 && crossProduct(P[top - 1], P[top], P[i]) <= 0) --top; P[++top] = P[i]; } P[++top] = P[0]; }
void solve() { double sum = 0;
if (N > 2) { GrahamScan(); FOR(i, 0, top) sum += dist(P[i], P[i + 1]); } else if (N == 2) sum = dist(P[0], P[1]) * 2;
cout << setprecision(5) << fixed << max(sum, l) << '\n'; }
int main() { int T; cin >> T; while (T--) { read(); solve(); } }
|
參考資料
UVa 11096 - Nails_小白菜又菜-CSDN博客