题意：

有n个点，每个点有个坐标，要从第一个点开始到第n个点结束。当在第i个点的时候，他下一步只能去第j个点，i,j满足$x_i<x_j$,从i到j需要花费$x_i*y_j-x_j* y_i$的能量。如果能量是负的，则表明它得到了供给。请输出从第一个点到第n个点的最小花费的路径，如果有多条具有相同的最小花费，输出字典序最小的。其中$y_1=y_n=0，0=x_1<x_2,x_3,...,x_{n−1}<x_n，0≤x_i,y_i≤10^9$。

思路：

看到$x_i*y_j-x_j*y_i$就想到叉积了，因为叉积的值表示的是以$\vec{a}$和$\vec{b}$为相邻边形成平行四边形的面积，由于从起点到终点肯定是沿着顺时针方向走一条路径，再从终点往起点连一条路，这样整条路径就围成了一个凸包，由于这是顺时针围成的，所以面积是负的（平常的凸包是逆时针围成的，面积是正的），因为代价要尽可能小，所以该面积就要尽可能大，所以就可以发现一定要走凸壳了。

关于面积是负的解释：

若a×b>0，表示a在b的顺时针方向上；

若a×b<0，表示a在b的逆时针方向上；

若a×b==0表示a和b共线，但不确定方向是否相同。

因为起点到终点是顺时针走的，所以对于i到j这两个点，i在j的逆时针方向上，所以$\vec{i}\times \vec{j}=x_i*y_j-x_j*y_i<0$，而这两个向量形成的面积肯定是正的，所以说面积是代价的相反数。

所以复习了一下Graham扫描法，这里有篇博客的图解挺好的：https://www.cnblogs.com/cjyyb/p/7260523.html。

学习到了这种思想，结合题目，就知道排序要先按照x从小到大，如果x相同按照y从大到小，如果y还是相同按照id从大到小。之后就是扫描，画一下图知道如果叉积>0，应该把栈顶弹掉，或者如果共线（叉积==0），为了字典序最小，如果id比栈顶小，也把栈顶弹掉。

注意有多个星球可以具有相同坐标，而且i,j满足$x_i<x_j$这些条件吧。

这里x,y要开ll，因为我写的代码里有x*x，会爆int。

代码：

typedef long long ll;
struct point
{
    ll x,y;//要开ll
    int id;
}a[200010],p[200010];
bool cmp1(point aa,point bb)
{
    if(aa.x!=bb.x)return aa.x<bb.x;
    if(aa.y!=bb.y)return aa.y<bb.y;
    return aa.id<bb.id;
}
int n,top;
double cross(point p0,point p1,point p2)//叉乘判断在左边还是右边
{
    return 1.0*(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
bool cmp(point p1,point p2)
{
    if(p1.x!=p2.x)return p1.x<p2.x;
    if(p1.y!=p2.y)return p1.y>p2.y;
    return p1.id<p2.id;
    return 0;
}
void graham()
{
    sort(a,a+n,cmp);
    /*for(int i=0;i<n;i++)
        printf("%d %d %d\n",a[i].x,a[i].y,a[i].id);*/
    top=1;
    p[0]=a[0];
    p[1]=a[1];//0,1入栈
    for(int i=2;i<n;i++)
    {
        if(a[i].x==a[i-1].x)continue;
        //栈顶和栈顶的前一个连线，如果当前点在右边的话，栈顶出栈，继续
        while((top&&((cross(p[top-1],p[top],a[i])>0)||(cross(p[top-1],p[top],a[i])==0&&a[i].id<p[top].id))))
            //printf("%d\n",i);
            top--;
        top++;
        p[top]=a[i];
    }
}
int main()
{
    //freopen("C:/Users/lenovo/Desktop/学习/2018HDUContest/G","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lld%lld",&a[i].x,&a[i].y);
            a[i].id=i+1;
        }
        graham();
        for(int i=0;i<top;i++)
            printf("%d ",p[i].id);
        printf("%d\n",p[top].id);
    }
    return 0;
}

/*
 1
 5
 0 0
 1 2
 1 1
 2 2
 2 0
 */