hdu 多校赛 Problem G. Interstellar Travel

【题目链接】

题目意思

题目：给定平面上 n 个点，起点横坐标最小，终点横坐标最大。每一个点都在 x 轴上方，每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。

给定平面上 n 个点，起点横坐标最小，终点横坐标最大。每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。 求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。

显然坐标相同的点里只保留编号最小的点最优。 将起点到终点的路径补全为终点往下走到无穷远处，再往左 走到起点正下方，再往上回到起点。 任意路径中回到起点部分的代价相同，观察代价和的几何意 义，就是走过部分的面积的相反数。 代价和最小等价于面积最大，故一定是沿着上凸壳行走。 显然起点、终点、凸壳的拐点必须要作为降落点。 对于共线的点 a1,a2,…,am，若一个点 i 的编号是 [i,m] 中最 小的，那么在此处降落可以最小化字典序。 时间复杂度 O(nlogn)。

首先将所有点按照从左到右，从上到下，输入编号从小到大的顺序进行排序，然后依次通过叉积的正负来判断是否需要删除前一个点。然后注意坐标相同的点里只保留编号最小的点最优，即当叉积为0时，编号小优先。

叉积的运用（此处在之后的凸包和极角排序会用用到）：
a×b>0 则说明 b在a的左上方
a×b<0 则说明b在a的右下方
例如： a=（x1,y1）,b=(x2,y2)
则 a×b=x1*y2-x2*y1;

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef struct node
{
    long long x;
    long long y;
    int id;
}Node;
Node que[200005];
Node ans[200005];
bool check(Node a, Node b, Node c)
{
    if ((b.x - a.x)*(c.y - a.y) == (b.y - a.y)*(c.x - a.x))
        return c.id < b.id;
    return ((b.x - a.x)*(c.y - a.y) > (b.y - a.y)*(c.x - a.x));
}
int main()
{
    //freopen("G.in", "r", stdin);
    //freopen("G.error", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%lld%lld", &que[i].x, &que[i].y);
            que[i].id = i + 1;
        }
        sort(que,que+n,[](Node a,Node b)
        {
            if (a.x == b.x)
            {
                if (a.y == b.y)
                    return a.id < b.id;
                return a.y > b.y;
            }
            return a.x < b.x;
        });
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            if (i != 0 && que[i].x == que[i - 1].x&&que[i].y == que[i - 1].y)
                continue;
            while (flag > 1 && check(ans[flag - 2], ans[flag - 1], que[i]))
                flag--;
            ans[flag++] = que[i];
        }
        for (int i = 0; i < flag; i++)
        {
            printf("%d%c", ans[i].id, i == flag - 1 ? '\n' : ' ');
        }
    }
}