【CodeVS1298】凸包周长 – 徐亦轲的博客

向总让我们买的数学书还挺好的啊。。有凸包模板程序蒯。。

于是蒯了一遍，改了改。。还挺爽的

以前自己打的时候各种直线垂直什么的特判到死。。写这个题只有40分。。

蒯永远是很爽的！

// <Graham.cpp> - 03/29/16 15:06:36
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int getint(){
	int res=0,fh=1;char ch=getchar();
	while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
	if(ch=='-')fh=-1,ch=getchar();
	while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
	return fh*res;
}
#define f(x) ((x)*(x))
const int MAXN=100002;
int n,X,Y;
struct point{
	int x,y;
	bool operator <(const point b) const{
		int v1x=x-X,v1y=y-Y,v2x=b.x-X,v2y=b.y-Y;
		int j=v1x*v2y-v2x*v1y;
		return !j?x>=b.x:j<0;
	}
}p[MAXN];
int s[MAXN];
int main(){
	freopen("Graham.in","r",stdin);
	freopen("Graham.out","w",stdout);
	n=getint();
	for(int i=0;i<n;i++)p[i].x=getint(),p[i].y=getint();
	int l=0;
	for(int i=1;i<n;i++)if(p[i].x<p[l].x||(p[i].x==p[l].x&&p[i].y<p[l].y))l=i;
	swap(p[0],p[l]);
	X=p[0].x,Y=p[0].y;
	sort(p+1,p+n);
	p[n]=p[0];
	int top=2;
	s[1]=0;s[2]=1;
	for(int i=2;i<=n;i++){
		while(top>1){
			int v1x=p[s[top]].x-p[s[top-1]].x,v1y=p[s[top]].y-p[s[top-1]].y,
				v2x=p[i].x-p[s[top]].x,v2y=p[i].y-p[s[top]].y;
			if(v1x*v2y-v2x*v1y<0)break;
			top--;
		}
		s[++top]=i;
	}
	double ans=0;
	for(int i=2;i<=top;i++)
		ans+=sqrt(double(f(p[s[i]].x-p[s[i-1]].x)+f(p[s[i]].y-p[s[i-1]].y)));
	printf("%.1lf",ans);
	return 0;
}

// <Graham.cpp> - 03/29/16 15:06:36

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int getint(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

#define f(x) ((x)*(x))

const int MAXN=100002;

int n,X,Y;

struct point{

int x,y;

bool operator <(const point b) const{

int v1x=x-X,v1y=y-Y,v2x=b.x-X,v2y=b.y-Y;

int j=v1x*v2y-v2x*v1y;

return !j?x>=b.x:j<0;

}

}p[MAXN];

int s[MAXN];

int main(){

freopen("Graham.in","r",stdin);

freopen("Graham.out","w",stdout);

n=getint();

for(int i=0;i<n;i++)p[i].x=getint(),p[i].y=getint();

int l=0;

for(int i=1;i<n;i++)if(p[i].x<p[l].x||(p[i].x==p[l].x&&p[i].y<p[l].y))l=i;

swap(p[0],p[l]);

X=p[0].x,Y=p[0].y;

sort(p+1,p+n);

p[n]=p[0];

int top=2;

s[1]=0;s[2]=1;

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

while(top>1){

int v1x=p[s[top]].x-p[s[top-1]].x,v1y=p[s[top]].y-p[s[top-1]].y,

v2x=p[i].x-p[s[top]].x,v2y=p[i].y-p[s[top]].y;

if(v1x*v2y-v2x*v1y<0)break;

top--;

}

s[++top]=i;

}

double ans=0;

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

ans+=sqrt(double(f(p[s[i]].x-p[s[i-1]].x)+f(p[s[i]].y-p[s[i-1]].y)));

printf("%.1lf",ans);

return 0;

}