2018 Multi-University Training Contest 3 1007 / hdu6325 Problem G. Interstellar Travel 凸包

Problem G. Interstellar Travel

题意：
给定平面上n个点，起点1 为(0,0)，终点 n 为(Xn, 0)，其它点的横坐标 0 <Xi<Xn，纵坐标 Yi >=0。每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。2≤n≤200000。 Shortest judge solution: 979 bytes
题解：
显然坐标相同的点里只保留编号最小的点最优。
将起点到终点的路径补全为终点往下走到无穷远处，再往左走到起点正下方，再往上回到起点。
任意路径中回到起点部分的代价相同，观察代价和的几何意义，就是走过部分的面积的相反数。
代价和最小等价于面积最大，故一定是沿着上凸壳行走。
显然起点、终点、凸壳的拐点必须要作为降落点。
对于共线的点a1,a2,...,am，若一个点i的编号是[i,m]中最小的，那么在此处降落可以最小化字典序。时间复杂度O(nlogn)。


1、其实首先要明确从点1 直接到点 n 的花费是 0，所以再加入其它点的代价必须为负。
2、根据叉积的几何意义，面积要最大，那就是求凸包。
3、最皮的是要字典序最小输出，也就是在凸包边界线上的点也有可能要取。所以我们记录一下边界线上的点是否小于它到拐点之间的点。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a; i<=b; ++i)
#define per(i,b,a) for (int i=b; i>=a; --i)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define fi  first
#define se  second
typedef long long ll;
const int N = 200005;

struct Point {
    ll  x, y;  int id;
    Point(ll x=0, ll y=0):x(x),y(y){} //构造函数，方便代码编写
};
typedef Point Vector;
Vector operator +(Vector A, Vector B){ return Vector(A.x+B.x, A.y+B.y); }
Vector operator -(Point A, Point B){ return Vector(A.x-B.x, A.y-B.y); }
bool operator <(const Point& a, const Point& b){
    if(a.x==b.x && a.y==b.y) return a.id < b.id;
    return a.x<b.x || (a.x==b.x && a.y<b.y);
}
ll  Cross(Vector A, Vector B){ return A.x*B.y - A.y*B.x; }

bool used[N];
int mi[N];
void ConvexHull(Point* p, int n, Point* ch)
{
    sort(p, p+n);
    int m = 0;
    for(int i=0; i<n; ++i) {  //维护上凸包
        if(i>1 && p[i].x==p[i-1].x && p[i].y==p[i-1].y) continue;
        while(m>1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])>0) --m;
        ch[m++] = p[i];
    }
    mes(used, false);
    used[0] = used[m-1] = true;
    for(int i=1; i<m; ++i) {
        if(Cross(ch[i]-ch[i-1], ch[i+1]-ch[i-1]) != 0)
            used[i] = true;
    }
    for(int i=m; i>=0; --i) {
        if(used[i]) mi[i] = ch[i].id;
        else  mi[i] = min(mi[i+1], ch[i].id);
    }
    for(int i=0; i<m; ++i)
        if(mi[i] == ch[i].id)
            printf("%d%c", ch[i].id, " \n"[i==m-1]);
}
Point p[N];
Point vertex[N];
int main()
{
    int T;  scanf("%d", &T);
    while(T--)
    {
        int n;  scanf("%d", &n);
        rep(i,1,n) scanf("%lld%lld", &p[i].x, &p[i].y), p[i].id=i;
        ConvexHull(p+1, n, vertex);
    }

    return 0;
}