Link：http://poj.org/problem?id=2007
Graham法求凸包（O(Nlog2N)）
/* 极角排序 */
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 100;
const double eps = 1e-6;
struct Point
{
double x,y;
};
Point a[N];
//是否严格左转，共线不算（叉乘）
double xmult(Point a,Point b,Point c) //(ca)×(cb)
{
return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);
}
// sort排序函数
bool cmp(const Point &a, const Point &b)//逆时针排序
{
Point origin;
// 设置原点
origin.x = origin.y = 0;
return xmult(origin,b,a)<eps;
}
int main()
{
int n=0;
while(scanf("%lf%lf",&a[n].x,&a[n].y)!=EOF)
++n;
// 极角排序，第一个空过去
sort(a+1,a+n,cmp);
for(int i=0; i<n; ++i)
printf("(%.0lf,%.0lf)\n",a[i].x,a[i].y);
return 0;
}
