tkdsheep-solution-0021

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
开飞机，很明显直接对这些点求一个凸包即可，给出的点是按x排序的，所以O(n)扫过去就行

每次扫到一个点x，就从栈里面抛出最近的两个点构成一个向量v，然后做叉积，看x在v的顺时针方向还是逆时针方向，是逆时针的话，栈就要抛出一个点继续比较，顺时针就直接将x入栈，扫下一个点
}}}

{{{
补一下叉积
double chaji(POINT sp,POINT ep,POINT np) //sp是原向量的起点，ep是原向量的终点，np是新加入的点 
{
    return (ep.x - sp.x) * (np.y - sp.y) - (np.x - sp.x) * (ep.y - sp.y);
    //结果为正，则np在（sp，ep）的逆时针方向
    //结果为0，共线
    //结果为负，则np在顺时针方向 
}
}}}

开飞机，很明显直接对这些点求一个凸包即可，给出的点是按x排序的，所以O(n)扫过去就行
每次扫到一个点x，就从栈里面抛出最近的两个点构成一个向量v，然后做叉积，看x在v的顺时针方向还是逆时针方向，是逆时针的话，栈就要抛出一个点继续比较，顺时针就直接将x入栈，扫下一个点

补一下叉积
double chaji(POINT sp,POINT ep,POINT np) //sp是原向量的起点，ep是原向量的终点，np是新加入的点 
{
    return (ep.x - sp.x) * (np.y - sp.y) - (np.x - sp.x) * (ep.y - sp.y);
    //结果为正，则np在（sp，ep）的逆时针方向
    //结果为0，共线
    //结果为负，则np在顺时针方向 
}