社区讨论

63pts WA on#8 9 10 11 求调

P2742【模板】二维凸包 / [USACO5.1] 圈奶牛Fencing the Cows参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m3mx2a8o
此快照首次捕获于
2024/11/18 19:02
去年
此快照最后确认于
2025/11/04 14:27
4 个月前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

#define db double
#define xi ps[i].x
#define yi ps[i].y
#define xj ps[j].x
#define yj ps[j].y
#define xk ps[k].x
#define yk ps[k].y

const int N = 100005;
int n, mi, top, ni, q[N];
db my, mx, res;
struct pt 
{
	db x, y;
	db mo() 
	{
		db x1 = mx - x, 
	       y1 = my - y;
		return sqrt(x1*x1 + y1*y1);
	}
	db mop(pt p) 
	{
		return sqrt((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y));
	}
	bool operator < (pt p) 
	{
		db c = (x-mx) / mo();
		db cp = (p.x-mx) / p.mo();
		return ((abs(c-cp)) > 5e-4 && c > cp) || (abs(c-cp) <= 5e-4 && mo() < p.mo());
	}
} ps[N];

inline bool wp(int i, int j, int k) 
{
	db x1 = xj - xi, 
	   y1 = yj - yi,
	   x2 = xk - xj,
	   y2 = yk - yj;
	return (x1*y2 - x2*y1) > -5e-4;
}

signed main() 
{
	freopen("P2742.txt", "r", stdin);
	scanf("%d", &n);
	my = (db)INT_MAX;
	for (int i = 1; i <= n; ++i) {
		scanf("%lf%lf", &xi, &yi);
		if (yi < my || (yi == my && xi < mx)) {
			mi = i;
			my = yi;
			mx = xi;
		}
	}
	swap(ps[1], ps[mi]);
	sort(ps+2, ps+n+1);
//	for (int i = 1; i <= n; ++i) printf("%d %.2lf %.2lf\n\n", i, xi, yi);
	q[1] = 1, q[2] = 2, top = 2;
	for (ni = 3; ni <= n; ++ni) {
		while (!wp(q[top-1], q[top], ni)) q[top--] = 0;
		q[++top] = ni;
//		for (int i = 1; i <= top; ++i) printf("%d %.2lf %.2lf \n", q[i], ps[q[i]].x, ps[q[i]].y);
//		printf("%d\n", ni);
	}
//	for (int i = 1; i <= n; ++i) printf("%d %lf %lf\n", i, px, py);
//	for (int i = 1; i <= top; ++i) printf("%d ", q[i]);
	for (int i = 1; i < top; ++i) {
		res += ps[q[i]].mop(ps[q[i+1]]);
	}
	res += ps[q[top]].mop(ps[1]);
	if (n >= 2) printf("%.2lf\n", res);
	else printf("0.00\n");
//	printf("%lf\n", 2 + 3*sqrt(2));
	return 0;
}
liangyanbang

回复

0 条回复,欢迎继续交流。

正在加载回复...