凸包melkman算法cpp

/* ac poj 1113
由于1113输入已经是个简单多边形，故可以直接用melkman求凸包o（n）复杂度
如果输入只是个点集合，就要先排序 再用melkman 复杂度为nlgn
排序可先按照x排，再y排
*/

#include
#include
#include


#define N 1002
#define pi 3.141592653589793

struct POINT{
	int xy;
};

int nlD[N*2]topbot;
POINT point[N];

inline double dis（POINT aPOINT b）{
	double x=a.x-b.x;
	double y=a.y-b.y;
	return sqrt（x*x+y*y）;
}


inline int cross（POINT aPOINT b）{
	return a.x*b.y-b.x*a.y;
}

int isleft（POINT oPOINT aPOINT b）{		//判断ab是不是在oa的左边
	POINT x;
	POINT y;
	x.x=a.x-o.x;
	x.y=a.y-o.y;
	y.x=b.x-a.x;
	y.y=b.y-a.y;
	return cross（xy）;
}

void melkman（）{
	int it;

	bot=n-1; top=n;
	D[top++]=0; D[top++]=1;

	for（i=2;i		if（isleft（point[D[top-2]]point[D[top-1]]point[i]）!=0） break;	//寻找第三个点 要保证3个点不共线！！
		D[top-1]=i;			//共线就更换顶点
	}

	D