Scrambled Polygon（凸包+极角排序）

Scrambled Polygon（凸包+极角排序）"/>

Scrambled Polygon（凸包+极角排序）

题目链接：Scrambled Polygon

先给出知识点的讲解链接：传送门

极角就是高中学的，极坐标系中的极角。
sort对结构体排序，不都有一个cmp的函数吗？就是这个函数。
我们都会按照一个参数来改，这回我们就按照极角来排序。

bool cmp(node a,node b)
{int f=mul(a,b,edge[0]);//以edge[0]点为三角形的角点，求他们的叉积，下面判断是顺时针方向，还是逆时针方向。if(f>0||f==0&&dis(a,edge[0])<dis(b,edge[0])) return 1;return 0;
}

思路：直接排序即可。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int maxn=1e5+9;
struct node
{int x,y;
}edge[maxn];double dis(node a,node b)
{return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
double mul(node a,node b,node c)
{return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
bool cmp(node a,node b)
{int f=mul(a,b,edge[0]);if(f>0||f==0&&dis(a,edge[0])<dis(b,edge[0])) return 1;return 0;
}int main()
{int len=0;while(~scanf("%d%d",&edge[len].x,&edge[len].y))len++;sort(edge,edge+len,cmp);for(int i=0;i<len;i++)printf("(%d,%d)\n",edge[i].x,edge[i].y);return 0;
}