【计算几何】【凸包】Gym - 101164H - Pub crawl

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int n;
struct Point{
	ll x,y;
	int id;
	Point(const ll &x,const ll &y){
		this->x=x;
		this->y=y;
	}
	Point(){}
};
typedef Point Vector;
bool cmp(const Point &a,const Point &b){
	return a.x!=b.x ? a.x<b.x : a.y<b.y;
}
Vector operator - (const Point &a,const Point &b){
	return Vector(a.x-b.x,a.y-b.y);
}
ll Cross(const Vector &a,const Vector &b){
	return a.x*b.y-a.y*b.x;
}
Point ps[5010],qs[10010];
int k;
bool vis[5010];
void convex_hull(){
	k=0;
	for(int i=0;i<n;++i)if(!vis[ps[i].id]){
		while(k>1 && Cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<=0){
			--k;
		}
		qs[k++]=ps[i];
	}
	for(int i=n-2,t=k;i>=0;--i)if(!vis[ps[i].id]){
		while(k>t && Cross(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<=0){
			--k;
		}
		qs[k++]=ps[i];
	}
	--k;
}
int main(){
//	freopen("h.in","r",stdin);
//	freopen("h.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%lld%lld",&ps[i].x,&ps[i].y);
		ps[i].id=i+1;
	}
	sort(ps,ps+n,cmp);
	int e=0;
	printf("%d\n",n);
	int I=0;
	int last;
	while(n-e>1){
		++I;
		convex_hull();
		int ID;
		if(I==1){
			ID=0;
		}
		else{
			for(int i=0;i<k;++i){
				if(last==qs[i].id){
					ID=i;
					break;
				}
			}
		}
		for(int i=ID;i<(ID==0 ? k-1 : k);++i){
			++e;
			vis[qs[i].id]=1;
			printf("%d%c",qs[i].id,e==n?‘\n‘:‘ ‘);
		}
		for(int i=0;i<ID-1;++i){
			++e;
			vis[qs[i].id]=1;
			printf("%d%c",qs[i].id,e==n?‘\n‘:‘ ‘);
		}
		if(ID==0){
			last=qs[k-1].id;
		}
		else{
			last=qs[ID-1].id;
		}
	}
	for(int i=0;i<n;++i) if(!vis[ps[i].id]){
		++e;
		printf("%d%c",ps[i].id,e==n?‘\n‘:‘ ‘);
	}
	return 0;
}