在一个阳光明媚的下午， Mr.Box与 hdu2202 最大三角形 相遇了，经过一番学习和思考，他最终AC了这道题，题面如下：

思路：

1. 利用graham算法算出所给点集中相连起来可以包围住所有点的子集P，如下图：

2. 暴力枚举子集P中任意三个点对，更新最大三角形面积。

不难看出，本题的关键在于求出子集P，下面介绍Graham扫描法：

1. 找出输入的点坐标中，优先最靠下，次优最靠左的点；

2. 以该点为原点平移坐标系；

3. 利用内置的atan2函数写cmp函数，将点集按照优先与x轴夹角最小，次优与原点最近的原则排序；

atan2函数：atan2(y, x)，C++中一种double类型的反正切函数，返回值为弧度，是点(0，0)和(x，y)的连线与X轴正半轴的夹角，其值域为 [-π，π] （当y=0时，可以取到±π），且在第一二象限为正，在第三四象限为负，无特殊头文件

bool cmp(point a, point b)
{
    if (atan2(a.y, a.x) != atan2(b.y, b.x))
        return atan2(a.y, a.x) < atan2(b.y, b.x);
    else return a.x < a.y;
} 
/* 先判断两点与x轴连线的的角度谁更小，相同则返回离原点更近的那个 */

4. 将点集中前两个元素分别入栈；

5. 遍历接下来点集中每个点，设为t，设栈顶元素为p1，栈顶下面一个元素为p0。则如果向量 p0p1 x p1p2 < 0，则将栈顶元素出栈，一直循环至叉积结果为正，再将t入栈；

bool cross_mul(point a, point b, point c) 
{
    int x1 = b.x - a.x, y1 = b.y - a.y;
    int x2 = c.x - a.x, y2 = c.y - a.y;
    return x1 * y2 - x2 * y1 > 0;
} // 返回向量ab叉乘bc是否为正

/* graham核心代码，n为输入点集容量，cnt为栈内元素个数，初始值为0 */
for (int i = 2; i < n; ++i) 
{
    while (i >= 0 && !cross_mul(stack[cnt - 2], stack[cnt - 1], p[i]))
        cnt--;
    stack[cnt++] = p[i];
}

6. 最后栈内的就都是凸包的边界点。

追加一个利用叉乘快速计算三角形面积的公式

S=|(x1*y2+x2*y3+x3*y1-y1*x2-y2*x3-y3*x1)/2|

OVER

最后记录一下最近听的《当爱已成往事》：

“不要问我是否再相逢，
不要管我是否言不由衷。”