HDU 6325 Problem G. Interstellar Travel(凸包)

题意:

给你n个点,第一个点一定是(0,0)，最后一个点纵坐标yn一定是0，中间的点的横坐标一定都是在(0,xn)之间的

 然后从第一个点开始飞行，每次飞到下一个点j，你花费的价值就是xi*yj-xj*yi，并且这里每一次飞行必须满足xi<xj

让你求出你所花费的最小的价值(可以为负)下，飞行的路径，如果有多种情况，输出路径字典序最小的那个

显然坐标相同的点里只保留编号最小的点最优。这里是因为题目严格要求xi<xj，所以不可能在原地飞行。

将起点到终点的路径补全为终点往下走到无穷远处，再往左走到起点正下方，再往上回到起点。任意路径中回到起点部分的代价相同，观察代价和的几何意义，就是走过部分的面积的相反数。代价和最小等价于面积最大，故一定是沿着上凸壳行走。

显然起点、终点、凸壳的拐点必须要作为降落点。对于共线的点a​1​​,a​2​​,...,a​m​​，若一个点ii的编号是[i,m]中最小的，那么在此处降落可以最小化字典序。

#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5 + 10;
typedef long long ll;
int n,m,ans[mx],top,ma;
struct node
{
    int x,y;
    int pos;
}s[mx],tubeg[mx],w;
bool vis[mx];
ll judge(node p1,node p2,node p0)//面积公式判断正负值 
{
    ll ans = 1ll*(p1.x-p0.x)*(p2.y-p0.y) - 1ll*(p2.x-p0.x)*(p1.y-p0.y);
    return ans; 
}
bool cmp(node a,node b)
{
    ll c = judge(w,b,a);//极角排序,同角度按距离从小到大排 
    if(b.x==a.x&&b.y==a.y) return a.pos > b.pos;
    if(!c) return pow(a.x-w.x,2)+pow(a.y-w.y,2) < pow(b.x-w.x,2)+pow(b.y-w.y,2);
    return c > 0;
}
void Graham()
{
    tubeg[0] = s[0],tubeg[1] = s[1];
    top = 2;
    for(int i=2;i<n;i++)
    {
        while(top>1&&judge(tubeg[top-2],s[i],tubeg[top-1])<=0)
        {
            if(judge(tubeg[top-2],s[i],tubeg[top-1])<0||tubeg[top-1].pos>s[i].pos) top--;
            else break;
        }
        tubeg[top++] = s[i];
    }
    for(int i=0;i<top;i++) printf("%d%c",tubeg[i].pos+1,i==top-1?'
':' ');
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++){
            scanf("%d%d",&s[i].x,&s[i].y);
            s[i].pos = i; 
        }
        w = s[0];
        sort(s+1,s+n,cmp);
        Graham();
    }
    return 0;
}