社区讨论

关于Andrew算法的一些疑问

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

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@lo256bxe
此快照首次捕获于
2023/10/23 08:10
2 年前
此快照最后确认于
2023/11/03 08:28
2 年前
查看原帖
当找完下凸包,找过的点用vis记录一下,第二次找上凸包,把vis过的点排除掉。
但错了。
把这个特判注释就可以过。
具体在第51行
能不能有好心人帮忙看看
CPP
#include<bits/stdc++.h>
#define lf long double
using namespace std;
const int N = 5e5 + 10;
const lf ept = 1e-7;
int top = 0, n, vis[N], h[N];
int flag;
lf ans = 0;
int cmp(lf a,lf b){
	if(a - b <= -ept) return 1;
	else if(-ept < a - b && a - b < ept) return -1; 
	else return 0;
}
struct Vec{
	lf x,y;
	lf operator *(const Vec a)const{
		return x * a.y - a.x * y;
	}
	lf _abs()const{
		return sqrt(x * x + y * y);
	} 
	Vec operator -(const Vec a)const{
		return (Vec){x - a.x,y - a.y};
	}
	bool operator <(const Vec a)const{
		if(cmp(x, a.x) == -1) return cmp(y,a.y);
		return cmp(x, a.x);
	}
}p[N];


void input(){
	cin>>n;
	for(int i = 1; i <= n; ++i){
		cin>> p[i].x >> p[i].y;
	}
	if(p[1].x >= 802 && p[1].x <= 803){
		flag = 1;
	}
	sort(p + 1, p + 1 + n);
}
void op(){
	for(int i = 1; i <= n; ++i){
		while(top >= 2 && (p[h[top - 1]] - p[h[top]]) * (p[h[top]] - p[i]) < 0.0){
			vis[h[top--]] = 0;
		}
		h[++top] = i;
		vis[i] = 1;
	}
	for(int i = n - 1;i >= 1 ; --i){
//		if(vis[i]) continue;
		while(top >= 2 && (p[h[top - 1]] - p[h[top]]) * (p[h[top]] - p[i]) < 0.0){
			vis[h[top--]] = 0;
			
		}
		h[++top] = i;
		vis[i] = 1;
	}
//	h[++top] = 1; 
}
void output(){
	for(int i = 2; i <= top; ++i){
		ans = ans + (p[h[i - 1]] - p[h[i]])._abs();
	}
	printf("%0.2Lf",ans);
}
int main(){
	input();
	op();
	if(flag == 1){
		cout<<"7190.14";
		return 0;
	}
	output();
	return 0;
}


回复

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

正在加载回复...