[BZOJ1670][Usaco2006 Oct]Building the Moat护城河的挖掘(凸包
发布时间:2020-12-14 01:19:47 所属栏目:大数据 来源:网络整理
导读:题目描述 传送门 题解 凸包裸题。 代码 #includealgorithm #includeiostream #includecstring #includecstdio #includecmath using namespace std ; #define N 5005 const double eps= 1e-9 ; int dcmp( double x){ if (x=epsx=-eps) return 0 ; return (x 0
题目描述传送门 题解凸包裸题。 代码#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define N 5005
const double eps=1e-9;
int dcmp(double x)
{
if (x<=eps&&x>=-eps) return 0;
return (x>0)?1:-1;
}
struct Vector
{
double x,y;
Vector(double X=0,double Y=0)
{
x=X,y=Y;
}
bool operator < (const Vector &a) const
{
return x<a.x||(x==a.x&&y<a.y);
}
};
typedef Vector Point;
Vector operator - (Vector a,Vector b) {return Vector(a.x-b.x,a.y-b.y);}
int n,top;
Point p[N],stack[N];
double ans;
double Dot(Vector a,Vector b)
{
return a.x*b.x+a.y*b.y;
}
double Len(Vector a)
{
return sqrt(Dot(a,a));
}
double Cross(Vector a,Vector b)
{
return a.x*b.y-a.y*b.x;
}
void graham()
{
sort(p+1,p+n+1);
top=0;
for (int i=1;i<=n;++i)
{
while (top>1&&dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0)
--top;
stack[++top]=p[i];
}
int k=top;
for (int i=n-1;i>=1;--i)
{
while (top>k&&dcmp(Cross(stack[top]-stack[top-1],p[i]-stack[top-1]))<=0)
--top;
stack[++top]=p[i];
}
if (n>1) --top;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
graham();
for (int i=1;i<=top;++i)
ans+=Len(stack[i%top+1]-stack[(i+1)%top+1]);
printf("%.2lfn",ans);
}
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |