[USACO5.1]二维凸包模板

传送门

Description

求\(n\)个点凸包的周长

Solution

计算几何打暴力必备

Code

#include<bits/stdc++.h>

#define reg register

#define ll long long

#define db double

using namespace std;

const int MN=1e5+5;

const db eps=1e-8;

int n;

struct Point{

	db x,y;

	Point(db x=0,db y=0):x(x),y(y){}

	db mo(){return sqrt(1.*x*x+1.*y*y);}

	Point operator-(const Point&o)const{return Point(x-o.x,y-o.y);}

	db operator^(const Point&o)const{return x*o.y-y*o.x;}

	bool operator <(const Point&o)const{return x<o.x||(x==o.x&&y<o.y);}

}p[MN];

int u[MN],d[MN],tu,td;

int main()

{

	scanf("%d",&n);

	reg int i;

	for(i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);

	std::sort(p+1,p+n+1);

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

	{

		while(tu>1&&((p[u[tu]]-p[u[tu-1]])^(p[i]-p[u[tu-1]]))>-eps) --tu;

		u[++tu]=i;

	}

	for(i=n;i;--i)

	{

		while(td>1&&((p[d[td]]-p[d[td-1]])^(p[i]-p[d[td-1]]))>-eps) --td;

		d[++td]=i;

	}

	db ans=0.;

	for(i=1;i<tu;++i) ans+=(p[u[i+1]]-p[u[i]]).mo();

	for(i=1;i<td;++i) ans+=(p[d[i+1]]-p[d[i]]).mo();

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

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

[USACO5.1]二维凸包模板

传送门

Description

Solution

Code

最新文章

热门文章