洛谷P2742 圈奶牛 （凸包 Andrew算法）

[USACO5.1] 圈奶牛Fencing the Cows /【模板】二维凸包

题目背景

upd: 新增一组 hack 数据。

题目描述

农夫约翰想要建造一个围栏用来围住他的奶牛，可是他资金匮乏。他建造的围栏必须包括他的奶牛喜欢吃草的所有地点。对于给出的这些地点的坐标，计算最短的能够围住这些点的围栏的长度。

输入格式

输入数据的第一行是一个整数。表示农夫约翰想要围住的放牧点的数目 $n$。

第 $2$ 到第 $(n+1)$ 行，每行两个实数，第 $(i+1)$ 行的实数 $x_i,y_i$ 分别代表第 $i$ 个放牧点的横纵坐标。

输出格式

输出输出一行一个四舍五入保留两位小数的实数，代表围栏的长度。

样例 #1

样例输入 #1

4
4 8
4 12
5 9.3
7 8

样例输出 #1

12.00

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$-10^6\le x_i,y_i\le 10^6$。小数点后最多有 $2$ 位数字。

思路

用 Convex_hull()函数求凸包，用unique()函数去重

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5 + 5;
const double eps = 1e-6;

int sgn(double x) {
	if (fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}

struct Point {
	double x, y;
	Point() {}
	Point(double x, double y) : x(x), y(y) {}
	Point operator + (Point B){return Point(x + B.x, y + B.y);}
	Point operator - (Point B){return Point(x - B.x, y - B.y);}
	Point operator * (double k) {return Point(x * k, y * k);}
	Point operator / (double k) {return Point(x / k, y / k);}
	bool operator == (Point B) {return sgn(x - B.x) == 0 && sgn(y - B.y) == 0;}
	// 按x坐标从小到大排序 若x坐标相同 按y坐标从小到大排序
	bool operator < (Point B) {
		return sgn(x - B.x) < 0 || (sgn(x - B.x) == 0 && sgn(y - B.y) < 0);
	}
};

typedef Point Vector;

double Cross(Vector A, Vector B) {
	return A.x * B.y - A.y * B.x;
}

double Dist(Point A, Point B) {
	return hypot(A.x - B.x, A.y - B.y);
}

int Convex_hull(Point *p, int n, Point *ch) {
	n = unique(p, p + n) - p; // 去除重复点
	sort(p, p + n);
	int v = 0;
	// 求下凸包 如果p[i]右拐弯 这个点不在凸包上 回退
	for (int i = 0; i < n; ++i) {
		while (v > 1 && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
			v--;
		ch[v++] = p[i];
	}
	int j = v;
	// 求上凸包
	for (int i = n - 2; i >= 0; --i) {
		while (v > j && sgn(Cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0)
			--v;
		ch[v++] = p[i];
	}
	if (n > 1) --v; // 在构造上凸包时，最后一个点和第一个点是重复的，因此我们需要减去 1，以确保没有重复的点。


	return v;
}


Point p[N], ch[N];
void solve() {
	int n; cin >> n;
	for (int i = 0; i < n; ++i) {
		scanf("%lf %lf", &p[i].x, &p[i].y);
	}
	int v = Convex_hull(p, n, ch); // 返回凸包顶点数
	double ans = 0;
	for (int i = 0; i < v; ++i) {
		ans += Dist(ch[i], ch[(i + 1) % v]);
	}
	printf("%.2f\n", ans);
}

int main() {
	int tt = 1; // cin >> tt;
	while (tt--) {
		solve();
	}
	

	return 0;
}