@Junlier
2018-09-18T11:38:29.000000Z
字数 1672
阅读 2326
数学方法——计算几何
题目:洛谷P2742[模板]二维凸包/[USACO5.1]圈奶牛Fencing the Cows
yyb的讲解:https://www.cnblogs.com/cjyyb/p/7260523.html
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<ctime>
#include<queue>
#include<stack>
#include<vector>
#define lst long long
#define ldb long double
#define N 50050
using namespace std;
const int Inf=1e9;
int read()
{
int s=0,m=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')m=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,top;
struct NODE{ldb x,y;}ljl[N],tb[N];
//tb[]用来储存在凸包上的点(数组模拟栈来维护)
//极角排序的cmp
bool cmp(const NODE &a,const NODE &b)
{
ldb A=atan2((a.y-ljl[1].y),(a.x-ljl[1].x));//就是那个角度(极角)
ldb B=atan2((b.y-ljl[1].y),(b.x-ljl[1].x));
if(A==B)return a.x<b.x;
return A<B;
}
/************************
计算叉积(向量之间)(向量用坐标法表示)
A×B>0 则说明B在A的左上方
A×B<0 则说明B在A的右下方
************************/
ldb Cross(NODE a,NODE b,NODE c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
void Get_tb()
{
NODE hh=(NODE){Inf,Inf};int kk=0;
for(int i=1;i<=n;++i)
if((ljl[i].y<hh.y)||(ljl[i].y==hh.y&&ljl[i].x<hh.x))
hh=ljl[i],kk=i;
swap(ljl[1],ljl[kk]);//先找一个凸包的“起点”放在第一个
sort(&ljl[2],&ljl[n+1],cmp);//极角排序
tb[0]=ljl[1],tb[top=1]=ljl[2];
for(int i=3;i<=n;++i)//按极角排序的顺序一个一个判断
{
while(top&&Cross(tb[top-1],ljl[i],tb[top])>=0)top--;
//如果凸包还存在 且 叉积>=0(新加的这个向量在从前向量的左上方)就要一直弹
tb[++top]=ljl[i];
}
}
ldb Dist(NODE a,NODE b)
{//两点之间的距离
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void Get_zc()
{
ldb C=0;
for(int i=1;i<=top;++i)
C+=Dist(tb[i-1],tb[i]);//凸包上两点的距离
if(top>1)C+=Dist(tb[top],tb[0]);//记得首尾相接
printf("%.2Lf\n",C);
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
scanf("%Lf%Lf",&ljl[i].x,&ljl[i].y);
Get_tb(),Get_zc();
return 0;
}