USACO/fc

来自NOCOW

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .1中的OI题目Fencing the Cows的介绍及题解，参见翻译，C语言代码，C++语言代码，Pascal语言代码。

[编辑] 问题分析

标准的凸包。
所谓凸包（这里说的是平面点集的凸包），就是一个最小的凸多边形，把所有给定点包含在内。显然，凸包一定是由给定的点中的某一些点构成。
下面介绍一种快速而且简便的凸包算法——Graham Scan。
预处理要对所有点进行排序。找出一个最左边的点，如果有多个再找最下边的。然后以这个点为准对其他所有点按照逆时针顺序排序（其实顺时针也可以，但是大多数人的习惯是逆时针），这里要用到向量叉积。
算法很简单
先开一个栈，分别放入第1、2、3个点（这三个点显然都在凸包中）。然后从第4个点开始枚举。如果栈顶元素指向当前点的有向线段与栈顶下方元素指向栈顶的有向线段构成右手系（就是说往右转啦，这里又要用到叉积），则栈顶元素出栈，重复以上过程直到这两个线段构成左手系，把当前点放入栈顶。这样到第n个点枚举完后，栈中的元素就构成了一个凸包，而且还是有序的。由于每个点最多入栈和出栈各一次，所以这个算法的时间复杂度是O(n)。加上先前排序的O(nlogn)，总的时间复杂度就是O(nlogn)。