Luogu P2742 模板-二维凸包

之前写的实在是太蠢了.于是重新写了一个.
用 \(Graham\) 算法求凸包.
注意两个向量 \(a\times b>0\) 的意义是 \(b\) 在 \(a\) 的左侧,于是可以用这个方法判断是否弹点.
写的时候注意细节:确定原点时的比较和排序时的比较是不同的,并且排序时不要把原点加入.

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define mp make_pair

#define pii pair<int,int>

inline int read()

{

	int x=0;

	bool pos=1;

	char ch=getchar();

	for(;!isdigit(ch);ch=getchar())

		if(ch=='-')

			pos=0;

	for(;isdigit(ch);ch=getchar())

		x=x*10+ch-'0';

	return pos?x:-x;

}

const int MAXN=1e4+10;

int n;

struct v2

{

	double x,y;

	v2(double x=0,double y=0):x(x),y(y) {}

	friend double operator * (const v2 &a,const v2 &b)

		{

			return a.x*b.y-a.y*b.x;

		}

	friend v2 operator + (const v2 &a,const v2 &b)

		{

			return v2(a.x+b.x,a.y+b.y);

		}

	friend v2 operator - (const v2 &a,const v2 &b)

		{

			return v2(a.x-b.x,a.y-b.y);

		}

	bool operator < (const v2 &rhs) const

		{

			return x==rhs.x?y<rhs.y:x<rhs.x;

		}

	double modulus()

		{

			return sqrt(x*x+y*y);

		}

	double angle()

		{

			return atan2(y,x);

		}

}p[MAXN];

v2 origin;

bool cmp(const v2 &a,const v2 &b)

{

	double a1=(a-origin).angle();

	double a2=(b-origin).angle();

	return a1==a2?a.x<b.x:a1<a2;

}

v2 stk[MAXN];

int tp=0;

void ConvexHull()

{

	for(int i=2;i<=n;++i)

		if(p[i]<p[1])

			swap(p[i],p[1]);

	origin=p[1];

	sort(p+2,p+n+1,cmp);

	for(int i=1;i<=n;++i)

		{

			while(tp>=2 && (stk[tp]-stk[tp-1])*(p[i]-stk[tp])<=0)

				--tp;

			stk[++tp]=p[i];

		}

	stk[++tp]=p[1];

}

double calcC()

{

	double s=0;

	for(int i=1;i<tp;++i)

		s+=(stk[i+1]-stk[i]).modulus();

	return s;

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i)

		{

			double x,y;

			scanf("%lf%lf",&x,&y);

			p[i]=v2(x,y);

		}

	ConvexHull();

	double ans=calcC();

	printf("%.2lf\n",ans);

	return 0;

}

巴特西

Luogu P2742 模板-二维凸包

Luogu P2742 模板-二维凸包

最新文章

热门文章