#define ll long long
struct Point{
int x,y;
}p[N];
Point ch[N];
bool cmp(Point x,Point y){
return x.x<y.x||(x.x==y.x&&x.y<y.y);//x从小到大排序，如果x相同则y从小到大排序
}
int Cross(Point x,Point y,Point z){
ll x1=x.x-y.x;
ll y1=x.y-y.y;
ll x2=z.x-y.x;
ll y2=z.y-y.y;
if((x1*y2-x2*y1)<=0) return 0;//在右边（关于 2. ）
return 1;
}
int main(){
sort(p,p+n,cmp);
int m=0;
//从左到右扫描
for(int i=0;i<n;i++){
while(m>1&&!Cross(ch[m-1],ch[m-2],p[i])) m--;
ch[m++]=p[i];
}
int k=m;
//从右到左扫描
for(int i=n-2;i>=0;i--){
while(m>k&&!Cross(ch[m-1],ch[m-2],p[i])) m--;
ch[m++]=p[i];
}
//删去重复的起点
if(n>1) m--;//凸包有m个顶点
return 0;
}
