凸包WA 0求调
查看原帖
凸包WA 0求调
716965
L_zaa_L楼主2024/1/4 16:55
/*
 * @Author: zaa
 * @Date: 2024-01-04 15:56:16
 * @LastEditTime: 2024-01-04 16:55:09
 * @FilePath: \code\1.4\P2742【模板】二维凸包.cpp
 * @about me: Sorry,I'm very vegetabble.
 */
#include<bits/stdc++.h>
#define int long long
#define double long double
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
using namespace std;
const int N=1e6+5;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
void chmx(int &x,int y){(x<y)&&(x=y);}
void chmn(int &x,int y){(x>y)&&(x=y);}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
int n;
struct P{
	double x,y;
}a[100005],st[100005];
double calc(P a1,P a2,P b1,P b2){
    return (a2.x-a1.x)*(b2.y-b1.y)-(b2.x-b1.x)*(a2.y-a1.y);
}
double d(P a,P b){
    return (double)sqrt(1.0*(b.y-a.y)*(b.y-a.y)+1.0*(b.x-a.x)*(b.x-a.x));
}
bool cmp(P x,P y){
    double c=calc(a[1],x,a[1],y);
    if(c>0) 
		return 1;
    if(c==0&&d(a[0],x)<d(a[0],y)) 
		return 1;
    return 0;
}
double mn;
signed main(){
	freopen("P2742_1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	n=read();
	int p=1;
	a[0].x=a[0].y=21474836470;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
		if(a[i].y<a[0].y){
			a[0]=a[i];
			p=i;
		}
		else if(a[i].y==a[0].y&&a[0].x>a[i].x){
			a[0]=a[i];
			p=i;
		}
	}
	swap(a[1],a[p]);
	sort(a+2,a+n+1,cmp);
	int cnt=1;
	st[cnt]=a[1];
	for(int i=2;i<=n;i++){
		while(cnt>1&&calc(st[cnt-1],st[cnt],st[cnt],a[i])<=0)
			cnt--;
		cnt++;
		st[cnt]=a[i];
	}
	st[++cnt]=a[1];
	double ans=0;
	for(int i=1;i<cnt;i++)
		ans+=d(st[i],st[i+1]);
	printf("%0.2Lf",ans);
#ifdef LOCAL
    Debug("\nMy Time: %.3Lfms\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}
2024/1/4 16:55
加载中...