# 題目: UVa 11096 - Nails

# 題目說明

給 N 個點 (x, y 平面座標)，求這些點形成的 凸包(Convex Hull) 周長

INPUT:
第一行輸入一個整數 T ，代表測資數
每筆測資輸入 L 、 N ，代表橡皮筋長度、點的數量
接下來有 N 行，每行輸入兩個變數 (x, y) ，為點的座標

OUTPUT:
輸出 MAX ( 凸包(Convex Hull) 周長， L )

將凸包算出後再兩兩計算長度，加總即為周長

涉及小數，所以題中變數盡量用 double

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <math.h>
	#include <iomanip>

	using namespace std;

	static auto fast_io = []
	{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	return 0;
	}();

	struct point
	{
	double x;
	double y;
	double d;
	};
	vector< point > V;
	vector< point > ret;
	int T, N;
	double L;

	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 init()
	{
	V.clear();
	ret.clear();
	}

	void read()
	{
	double a, b;
	cin >> L >> N;
	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);

	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]);
	}
	ret.emplace_back(V[0]);
	}

	void print()
	{
	double ans = 0;
	for (int i = 1; i < ret.size(); ++i) ans += dist(ret[i - 1], ret[i]);

	cout << setprecision(5) << fixed << max(ans, L) << "\n";
	}

	int main()
	{
	cin >> T;
	while (T--)
	{
	init();
	read();
	GrahamScan();
	print();
	}
	}

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <math.h>
	#include <iomanip>

	using namespace std;

	struct point
	{
	double x;
	double y;
	};

	int T, N;
	double L;
	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 a, b;
	cin >> L >> N;
	for (int i = 0; i < N; ++i) cin >> a >> b, V.push_back({ a, b });
	}

	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]);
	}
	}

	double dis(point& a, point& b)
	{
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
	}

	void print()
	{
	double ans = 0;
	for (int i = 0; i < ret.size() - 1; ++i) ans += dis(ret[i], ret[i + 1]);

	cout << setprecision(5) << fixed << max(ans, L) << "\n";
	}

	int main()
	{
	cin >> T;
	while (T--)
	{
	init();
	read();
	Andrews_Monotone_Chain();
	print();
	}
	}

https://github.com/morris821028/UVa/blob/master/volume110/11096%20-%20Nails.cpp
https://blog.csdn.net/mobius_strip/article/details/8453882