HDU 6325 Interstellar Travel（凸包）

题目链接：Interstellar Travel

题意

在一个二维平面上总共有 n$n$ 个点，坐标分别为 (xi,yi)$(x_i,y_i)$，小 Q$Q$ 要从坐标为 (x1,y1)$(x_1,y_1)$ 的点到达坐标 (xn,yn)$(x_n,y_n)$ 的点，他每次只能从横坐标小的点到达横坐标大的点，即 xstart<xto$x_{start}<x_{to}$，如果他要从坐标为 (xi,yi)$(x_i,y_i)$ 的点到达 (xj,yj)$(x_j,y_j)$ 的点，则需要的代价为 xi×yj−xj×yi$x_i\times y_j-x_j\times y_i$，问要完成目标的最小代价。

输入

第一行为一个整数 T (1≤T≤10)$T(1\le T\le 10)$，接下去有 T$T$ 组数据，每组数据第一行为一个整数 n (2≤n≤2×105)$n(2\le n\le 2\times {10}^5)$，接下去 n$n$ 行每行两个整数 xi,yi (0≤xi,yi≤109)$x_i,y_i(0\le x_i,y_i\le {10}^9)$，数据保证 y1=yn=0,0=x1<x2,x3,⋯,xn−1<xn$y_1=y_n=0,0=x_1<x_2,x_3,\cdots ,x_{n-1}<x_n$。

输出

每组数据输出一个序列 p1,p2,⋯,pm (1≤pi≤n)$p_1,p_2,\cdots ,p_m(1\le p_i\le n)$，表示小 Q$Q$ 选择的路径为 p1→p2→⋯→pm$p_1\to p_2\to \cdots \to p_m$，pi$p_i$ 表示路径上第 i$i$ 个点的编号为 pi$p_i$，点的编号按输入顺序从 1$1$ 到 n$n$ 确定，其中 p1=1,pm=n$p_1=1,p_m=n$，如果有多组解，输出字典序最小的一组。

样例

输入

1
3
0 0
3 0
4 0

输出

1 2 3

题解

起点为 (0,0)$(0,0)$，且经过两个点的代价为两个点对应的向量叉积，即这两点与原点构成的三角形面积，若从向量 i$i$ 到向量 j$j$ 是以顺时针旋转，则这两个向量的叉积就为负数，为了使代价最小，也就是使负数的绝对值——三角形的面积最大，因此这条路径就是从原点到终点的一个凸壳。
首先对所有点去重，然后构造凸壳，构造过程中保留凸壳上的共线点，所有拐点必然是要作为答案的，但是共线点上可能存在比下一个拐点编号更小的点，为使答案的字典序最小，必须选择这些共线点上编号小于下一个拐点的一系列点，且这一系列点的字典序也要最小，在这些共线点中可以用单调栈来维护需要选择的字典序最小的点的编号。

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

#define LL long long
const int maxn = 200000 + 100;
struct Point {
    int x, y;
    int Index;
    Point() {}
    Point(int xx, int yy) {
        x = xx;
        y = yy;
    }
};

bool operator<(const Point &a, const Point &b) {
    return a.x == b.x? a.y < b.y: a.x < b.x;
}

LL operator^(const Point &a, const Point &b) {
    return (LL)a.x * b.y - (LL)a.y * b.x;
}

Point operator-(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}

bool operator!=(const Point &a, const Point &b) {
    return a.x != b.x || a.y != b.y;
}

int T, n, top, cnt, Mon_top;
Point point[maxn], sta[maxn], p[maxn], Mon_sta[maxn];
map<int, int> mp;

int main() {
    #ifdef LOCAL
        freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // LOCAL
    ios::sync_with_stdio(false);

    scanf("%d", &T);
    while(T--) {
        mp.clear();
        cnt = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i) {
            scanf("%d%d", &point[i].x, &point[i].y);
            point[i].Index = i;
            mp[point[i].x] = max(mp[point[i].x], point[i].y);
        }
        sort(point + 1, point + 1 + n);
        p[0].x = p[0].y = -1;
        for(int i = 1; i <= n; ++i) {
            if(point[i].y == mp[point[i].x]) {
                if(point[i] != p[cnt]) {
                    p[++cnt] = point[i];
                } else if(point[i].Index < p[cnt].Index) {
                    p[cnt] = point[i];
                }
            }
        }
        top = 0;
        for(int i = 1; i <= cnt; ++i) {
            while(top > 1 && ((sta[top - 1] - sta[top - 2]) ^ (p[i] - sta[top - 2])) > 0) {
                --top;
            }
            sta[top++] = p[i];
        }
        printf("1");
        for(int i = 0; i < top - 1; ) {
            int End = i + 1;
            while(End + 1 < top && ((sta[End + 1] - sta[End]) ^ (sta[End] - sta[i])) == 0) {
                ++End;
            }
            Mon_top = 0;
            for(int j = i + 1; j <= End; ++j) {
                while(Mon_top > 0 && sta[j].Index < Mon_sta[Mon_top - 1].Index) {
                    --Mon_top;
                }
                Mon_sta[Mon_top++] = sta[j];
            }
            for(int j = 0; j < Mon_top; ++j) {
                printf(" %d", Mon_sta[j].Index);
            }
            i = End;
        }
        printf("\n");
    }

    return 0;
}