求助,63pts,wa后4个点,拍了几千组了,无小hack啊
查看原帖
求助,63pts,wa后4个点,拍了几千组了,无小hack啊
222341
twocats楼主2024/10/14 08:23
#include<bits/stdc++.h>
//#define int long long
#define F(i,j,k) for(register int i=j,end=k;i<=end;i++)
#define D(i,j,k) for(register int i=j,end=k;i>=end;i--)
#define FV(i,v) for(register int i=0,end=v.size();i<end;i++)
#define FG(i,u) for(register int i=h[u];i;i=e[i].next)
#define FZ(i,n) for(register int i=0,end=1<<n;i<end;i++)
#define IT(i,A,x) for(register int i=A[x];i!=x;i=A[i])
#define init(A,x) memset(A,x,sizeof(A))
#define pb push_back
#define To e[i].to
#define mid ((l+r)>>1)
#define ls (u<<1)
#define rs (u<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define inf 0x3FFFFFFF
#define N 2000005
using namespace std;

struct Point
{
	double x;
	double y;
	bool operator < (const Point & T) const
	{
		if(x==T.x)	return y<T.y;
		return x<T.x;
	}
	Point operator - (const Point &T) const
	{
		Point res;
		res.x=x-T.x;
		res.y=y-T.y;
		return res;
	}
	Point operator + (const Point &T) const
	{
		Point res;
		res.x=x+T.x;
		res.y=y+T.y;
		return res;
	}
	int operator * (const Point &T) const
	{
		return -x*T.y+y*T.x;
	}
}p[N];

int n,top,tp,stk[N],vis[N];

double ans;

inline void ri(int &x)
{
	x=0;
	bool f=0;
	char c=getchar();
	while((c<48||c>57)&&c!='-')	c=getchar();
	if(c=='-')	f=1,c=getchar();
	while(c>47&&c<58)	x=x*10+c-48,c=getchar();
	x*=f?-1:1;
}

double len(Point p)
{
	return sqrt(p.x*p.x+p.y*p.y);
}

int main()//mmd,negative reading again!
{
//	freopen("1.txt","r",stdin);
//	freopen("2.txt","w",stdout);
	ri(n);
	F(i,1,n)	scanf("%lf%lf",&p[i].x,&p[i].y);
	sort(p+1,p+n+1),stk[++top]=1;
	F(i,2,n)
	{
		while(top>1&&(p[stk[top]]-p[stk[top-1]])*(p[i]-p[stk[top]])<=0)	vis[stk[top--]]=0;
		vis[i]=1,stk[++top]=i;
	}
	init(vis,0),tp=top;
	D(i,n-1,1)
	{
		if(vis[i])	continue;
		while(tp>top&&(p[stk[tp]]-p[stk[tp-1]])*(p[i]-p[stk[tp]])<=0)	vis[stk[tp--]]=0;
		vis[i]=1,stk[++tp]=i;
	}
//	puts("**********");
//	F(i,1,tp)	printf("*******%.1lf %.1lf\n",p[stk[i]].x,p[stk[i]].y);
	F(i,2,tp)	ans+=len(p[stk[i]]-p[stk[i-1]]);
	printf("%.2lf",ans);
	return 0;
}
2024/10/14 08:23
加载中...