``凸包详解：点击打开链接`点击打开链接`
``````
``````
``````#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
const int INF = 50005;

struct node
{
double x,y;
};

node data[INF];

node res[INF];				//数组模拟栈(这里如果用stl自带的栈会比较麻烦)

double Graham(node* data,node* res, int n);

double cross(node a, node b, node mark);  //求向量mark->a, 向量mark-> b的叉积；

double dis(node a, node b);    //求a,b两点距离；

long long  dis1(node a, node b);

bool cmp(node a,node b)
{
double ans = cross(a,b,data[0]);
if(ans > 0 || (ans == 0 && dis(a,data[0]) < dis(b,data[0]))) return true;
return false;
}

/*
8
0 0
2 0
4 0
4 2
4 4
2 4
0 4
0 2

4
0 1
0 2
0 3
0 4

*/

int main()
{
int n;
scanf("%d", &n);				//点集的大小

for(int i = 0; i < n; i++)
scanf("%lf %lf",&data[i].x,&data[i].y);

int len = Graham(data,res,n);	//凸包的大小(也就是凸包所包含点的数目)

long long  max = -1;
for(int i = 0; i <len; i++)
{
printf("%lf %lf\n",res[i].x,res[i].y) ;		//输出凸包
}

return 0;
}

double Graham(node* data,node* res, int n)
{
//求出最左下的那个点(原点或参照点)，并将此点和data[0]交换一下-------------------------
int t = 0;

for(int i = 1; i <n; i++)
{
if(data[t].y > data[i].y || (data[t].y == data[i].y) && data[t].x > data[i].x)
t = i;
}

node temp = data[t];
data[t] = data[0];
data[0] = temp;

//将除了data[0]之外的点按与data[0]的极角从小到大排序-----------------------

/*	如果用注释的部分来排序会很慢，所以用快排
for(int i = 1; i < n; i++)
{
int t = i;

for(int j =i+1; j < n; j++)
{
double flag = cross(data[t],data[j],data[0]);
if(flag < 0 || ( flag == 0 && dis(data[t],data[0]) > dis(data[j], data[0]) ) )
t = j;
}
node temp1 = data[t];
data[t] = data[i];
data[i] = temp1;
}
*/
sort(data + 1,data + n,cmp);

//初始化栈res----------------------------------------------------------------
res[0] = data[0];

int top = 0;

//利用栈不断维护凸壳----------------------------------------------------------

for(int i = 1; i < n; i++)
{
while(top > 0 && cross(res[top-1], data[i] ,res[top]) >= 0)				//找出所有右转的点，然后弹出栈
top--;
res[++top] = data[i];
}

}
double cross(node a, node b, node mark)
{
return (a.x - mark.x) * (b.y - mark.y) - (b.x - mark.x) * (a.y - mark.y);
}

double dis(node a, node b)
{
return sqrt( (a.x -b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) );
}
``````