这个问题应该是我卡住了,就算大家有人不会这个题也可以解决,求耐心看帖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
在上一个循环已经处理过了,但是如果讲这句话删掉, 会出现问题
请问这是为什么?