P2742 【模板】二维凸包 by HydraNazis
Trinity
2018-07-22 19:32:55
# P2742 【模板】二维凸包 / [USACO5.1]圈奶牛Fencing the Cows
## 题目描述
在二维坐标系上有 $n$ 个点，现知它们的坐标，试求出用线段把所有的点围住需要的最短长度，即二维凸包的周长。
## 分析
其实照百度说，解决二维凸包有五种算法，但还是Graham算法最为实用（虽然算法复杂度不是最低的，$O(nlogn)$而已)，对付大多数问题都可以解决。
## 解决
需掌握的几个知识：
$1$ . 叉积的性质：以 $\vec{a}$ 和 $\vec{b}$ 为边的平行四边形的面积。
$~~~~~~~~~~~~~~~\vec{a}\times \vec{b}=x_1\times y_2-x_2\times y_1$
$~~~~~~~~~~~~~~~\vec{a}\times \vec{b}<0(\ \vec{b}$ 在 $\vec{a}$左上方$)$
$~~~~~~~~~~~~~~~\vec{a}\times \vec{b}>0(\ $相反 $ )$
由这个性质可得：
有三点，一未知 $A$ 二已知 $B$, $C$ ，若 $A$ 与 $B$ , $C$叉乘都小于 $0$ , 就可以知道三者的基本位置关系。以此为例，我们可以判断得到每三个点之间的关系，知道是上凸包还是下凸包，和极角大小，通过这来构建凸包(也可以通过斜率来判断，反正斜率好写一些，我使用的是斜率）。
$2$ . 我们将点排个序，以点的纵坐标为排序基准，找到图最下方的点，一定是凸包上的一个点。然后以它为起点，离他最近的点为$2$号点（加入栈中），就用这来慢慢构建凸包。
$3$ . 我们把整个凸包分成上凸包（下降）和下凸包（上升），然后加栈，如果递增且极角较小，我们就把这加入栈中，而后来证明不是凸包上的节点就弹出栈。因为我们是分成两部分计算，就分别统计一下线段长，最后加在一起即可（这题不建议使用系统栈，因为很坑，自己试试就知道）。
我们图解开始（其实文字已经说的很明白）：
上代码（如有雷同，就当是我抄的）
```cpp
struct node{double x,y;}point[N];
int n,top=2,st[N];//top->栈顶，st->记录凸包上点的栈。
double ans,data_x,data_y;
inline double power(double x){return x*x;}
inline double dis(int a,int b){return sqrt(power(point[a].x-point[b].x)+power(point[a].y-point[b].y));}//两点间距离。
inline bool judge(int a,int b,int c)
{
return (point[a].y-point[b].y)*(point[b].x-point[c].x)>(point[a].x-point[b].x)*(point[b].y-point[c].y);//算斜率，乘在一起避免掉精。
}
inline bool cmp(node a,node b){return (a.y==b.y)?(a.x<b.x):(a.y<b.y);}//纵坐标小的在前，若相等，就取横坐标小的。
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&point[i].x,&point[i].y);
}
sort(point+1,point+n+1,cmp);
st[1]=1,st[2]=2;//前两点已经确定，入栈。
for(int i=3;i<=n;i++)//枚举其他的节点从3开始。
{
while(top>1&&!judge(i,st[top],st[top-1]))top--;//后者斜率（极角）小。
st[++top]=i;//重新入栈。
}
for(int i=1;i<=top-1;i++)ans+=dis(st[i],st[i+1]);
top=2;
memset(st,0,sizeof(st));//最好memset一下，有可能出问题。
st[1]=1,st[2]=2;
for(int i=3;i<=n;i++)
{
while(top>1&&judge(i,st[top],st[top-1]))top--;//把！去掉就可以了。
st[++top]=i;
}
for(int i=1;i<=top-1;i++)ans+=dis(st[i],st[i+1]);//后一边基本一样。
printf("%.2lf",ans);
return 0;
}
```
## 总结
$1$ . 打完题解后，感觉还是有的说的不清楚（就像我看别人的题解时一样），现在拿出参考资料，不懂的话，大家可以看一下[百度百科：凸包](https://baike.baidu.com/item/%E5%87%B8%E5%8C%85/179150?fr=aladdin)和[数学：凸包算法详解](https://www.cnblogs.com/aiguona/p/7232243.html)。
$2$ . 打完这题可以看一看月赛的 $E$ 题 ( 有难度 ），[P4756 Added Sequence](https://www.luogu.org/problemnew/show/P4756)。