一个非常不理解的问题
查看原帖
一个非常不理解的问题
199459
Masna_Kimoyo楼主2022/1/20 16:15

这个问题应该是我卡住了,就算大家有人不会这个题也可以解决,求耐心看帖qwq

这是我的代码:(可忽略)

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	double x,y;
	inline bool operator <(const node &a) const{
		return a.x==x?a.y<y:a.x<x;
	}	
}p[N];
int n,cnt;
int s[N];
double ans;
inline int read(){
	int x=0;
	bool w=0;
	char c=getchar();
	while(!isdigit(c))	w|=c=='-',c=getchar();
	while(isdigit(c))	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
#define printlf(x) print(x),putchar('\n')
#define printsp(x) print(x),putchar(' ')
inline void print(int x){
	if(x<0)	x=-x,putchar('-');
	if(x>9)	print(x/10);
	putchar('0'+x%10);
}
inline node getvec(node a,node b){
	return (node){a.x-b.x,a.y-b.y};
}
inline double dis(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double xmul(node a,node b){
	return (a.x*b.y)-(b.x*a.y);	
}
int main(){
	n=read();
	for(register int i=1;i<=n;++i)	cin>>p[i].x>>p[i].y;
	sort(p+1,p+n+1);
	s[++cnt]=1;
	for(register int i=2;i<=n;++i){
		node a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		while(xmul(a,b)<0 && cnt>1)	--cnt,a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		s[++cnt]=i;
	}
	s[++cnt]=n;
	for(register int i=n-1;i;--i){
		node a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		while(xmul(a,b)<0 && cnt>1)	--cnt,a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		s[++cnt]=i;
	}
//	for(register int i=1;i<=cnt;++i)
//		cout<<s[i]<<' '<<s[i+1]<<endl;
	for(register int i=1;i<cnt;++i)	ans+=dis(p[s[i]],p[s[i+1]]);
	printf("%.2lf",ans);
	return 0;
}

在一个地方:

	for(register int i=2;i<=n;++i){
		node a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		while(xmul(a,b)<0 && cnt>1)	--cnt,a=getvec(p[s[cnt-1]],p[s[cnt]]),b=getvec(p[s[cnt]],p[i]);
		s[++cnt]=i;
	}
	s[++cnt]=n;

随意理解一下代码,可以发现这里s[++cnt]=n在上一个循环已经处理过了,但是如果讲这句话删掉, 会出现问题

请问这是为什么?

2022/1/20 16:15
加载中...