[洛谷2742]凸包模闆

洛谷2742

凸包模闆

Code：

#include<bits/stdc++.h>
#define db double
using namespace std;
inline int read(){
	int res=0,f=1;char ch=getchar();
	while(!isdigit(ch)) {if(ch=='-') f=-f;ch=getchar();}
	while(isdigit(ch)) {res=(res<<1)+(res<<3)+(ch^48);ch=getchar();}
	return res*f;
}
const int N=1e5+5;
struct point{
	db x,y;
	point(){}
	point(db _x,db _y): x(_x),y(_y) {}
	friend inline point operator - (const point &a,const point &b) {return point(a.x-b.x,a.y-b.y);}
	friend inline db operator * (const point &a,const point &b) {return a.x*b.y-a.y*b.x;}
	inline db dis() {return sqrt(x*x+y*y);}
}p[N],q[N];
int n,tot=0;
inline bool cmp(point a,point b){
	db det=(a-p[1])*(b-p[1]);
	if(det) return det<0;
	return (a-p[1]).dis()<(b-p[1]).dis();
}
inline void graham(){
	int t=1;
	for(int i=2;i<=n;i++) {if(p[i].x<p[t].x || (p[i].x==p[t].x && p[i].y<p[t].y)) t=i;}
	swap(p[1],p[t]);
	sort(p+2,p+n+1,cmp);
	q[++tot]=p[1],q[++tot]=p[2];
	for(int i=3;i<=n;i++){
		while(tot>1 && (p[i]-q[tot-1])*(q[tot]-q[tot-1])<=0) --tot;
		q[++tot]=p[i];
	}
	q[++tot]=q[1];
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y);
	graham();
	db ans=0;
	for(int i=1;i<tot;i++) ans+=(q[i+1]-q[i]).dis();
	printf("%.2lf",ans);
	return 0;
}