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

平面上n个点，点之间沿直线走，规划一条路线，每次只能往左半平面的点走，走过最多的点。

显然所有的点都能走过。

n^2的暴力显然是每次找左边与其所形成夹角最小的点，但这样过不了（卡常数？）。

或者每轮不断求凸包。有个非常巧妙的地方是将每一轮输出后剩下的最后一个点加到下一轮的点里面一起求凸包，这样只要按逆时针输出每一轮，就能满足。

#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;
}