/*?ac?poj?1113
由于1113輸入已經(jīng)是個(gè)簡(jiǎn)單多邊形，故可以直接用melkman求凸包o（n）復(fù)雜度
如果輸入只是個(gè)點(diǎn)集合，就要先排序?再用melkman?復(fù)雜度為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;	//尋找第三個(gè)點(diǎn)?要保證3個(gè)點(diǎn)不共線！！
		D[top-1]=i;			//共線就更換頂點(diǎn)
	}

	D