凸包（Graham扫描法构建）

PS:我的妈呀，心态爆炸，好像也不太难，看各种模板看的云里雾里的，真的还是自己动手敲来的好，几乎没多久就懂的差不多了。。。。
一个本该寒假就该掌握的知识，居然熬了我几个小时。。。。。。。

这一次还是很好的了解了凸包，以前看群里学长们说，觉得好高大上，好难的样子，仔细了解后发现其实也没有想象中的那么恐怖

凸包基本概念：

这就是一个简单的凸包：

其实凸包求法有很多种：比如卷包裹法（时间复杂度O(n*n)）、Graham扫描法（时间复杂度O(nlogn）、Jarvis步进法、Melkman算法（时间复杂度O(n)）

好像Melkman算法要好一点，但是Graham扫描法更加实用，于是就找资料恶补了下：
步骤：

1、把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
2、把所有点的坐标平移一下，使 P0 作为原点，如上图。
3、计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道，结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。
（以上是准备步骤，以下开始求凸包）
4、以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：
连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。
如果在直线的右边就执行步骤5；如果在直线上，或者在直线的左边就执行步骤6。
5、如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
6、当前点是凸包上的点，把它压入栈，执行步骤7。
7、检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。如果不是的话就把 P2 后面那个点做当前点，返回步骤4。

步骤说明是参考这位大佬的博客：链接

Granham算法本质：

基本上就可以分为两个部分：
1、排序：（时间复杂度O(nlogn)）
排序时，有两种排序方式：
1、极角序（目前这种排序好像比较常见）：

2、水平序：

2、扫描；（时间复杂度O(n)）
扫描过程也就是上面步骤中逐步试探进栈出栈的过程；

虽然这些没多久就看懂了，但是写代码时，迟迟不敢动手，如果早些尝试，可能就不会耗这么长时间了⑧

于是边尝试，边看大牛的代码最终敲成了。。。。

当然这个代码是为了解决
给定若干点，求所构成的三角形面积的最大值

暴力时间复杂度O(nnn)，很显然TLE
于是：通过求得凸包，然后在凸包中进行筛选，最后A了

#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<iostream> using namespace std; typedef struct { double x,y; }POINT; POINT p[50010]; POINT result[50010]; /**叉乘*/ double multi(POINT p1,POINT p2,POINT p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p1.y-p0.y)*(p2.x-p0.x); } /**求距离*/ double Distance(POINT a,POINT b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } /**核心*/ int cmp(POINT a,POINT b) { double x=multi(a,b,p[0]); /**接下来就是为什么Granham算法比较核心的部分了， 正是因为这个排序才使得其时间复杂度大大降低*/ if(x>0) return 1; /**这就是在开始所说的共线问题的处理*/ else if(x==0&&Distance(a,p[0])<Distance(b,p[0])) return 1; return 0; } int main() { int n; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); /**p0表示纵坐标最小，横坐标最小的点*/ POINT p0; p0.x=p[0].x; p0.y=p[0].y; int t=0; //用来记录p0的位置，好最终与p[0]进行交换 for(int i=1;i<n;i++) { if(p[i].y<p0.y) { p0.y=p[i].y; t=i; } else if(p[i].y==p0.y&&p[i].x<p0.x) { p0.x=p[i].x; t=i; } } /**p[0]与p[t]进行交换，好方便之后的排序操作*/ swap(p[0],p[t]); sort(p+1,p+n,cmp); //排序 /**扫描操作*/ result[0]=p[0]; result[1]=p[1]; result[2]=p[2]; int top=2; for(int i=3;i<n;i++) { while(multi(p[i],result[top],result[top-1])>=0) top--; //出栈 result[++top]=p[i]; //圧栈 } //到这凸包就已经构建完成了 double s=0; for(int i=0;i<=top;i++) { for(int j=0;j<=top&&j!=i;j++) { for(int k=0;k<=top&&k!=j&&k!=i;k++) { POINT A=result[i]; POINT B=result[j]; POINT C=result[k]; double num=0.5*fabs(multi(B,C,A)); //0.5和fabs都得注意 if(num>s) s=num; } } } printf("%.2f\n",s); } return 0; }