HDU 6325 Interstellar Travel【凸包】

题目链接

Problem Description

After trying hard for many years, Little Q has finally received an astronaut license. To celebrate the fact, he intends to buy himself a spaceship and make an interstellar travel.
Little Q knows the position of n planets in space, labeled by 1 to n. To his surprise, these planets are all coplanar. So to simplify, Little Q put these n planets on a plane coordinate system, and calculated the coordinate of each planet (xi,yi).
Little Q plans to start his journey at the 1-th planet, and end at the n-th planet. When he is at the i-th planet, he can next fly to the j-th planet only if xi < xj, which will cost his spaceship xi×yj−xj×yi units of energy. Note that this cost can be negative, it means the flight will supply his spaceship.
Please write a program to help Little Q find the best route with minimum total cost.

Input

The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases.
In each test case, there is an integer n(2≤n≤200000) in the first line, denoting the number of planets.
For the next n lines, each line contains 2 integers xi,yi(0≤xi,yi≤109), denoting the coordinate of the i-th planet. Note that different planets may have the same coordinate because they are too close to each other. It is guaranteed that y1=yn=0,0=x1 < x2,x3,…,xn−1 < xn.

Output

For each test case, print a single line containing several distinct integers p1,p2,…,pm(1≤pi≤n), denoting the route you chosen is p1→p2→…→pm−1→pm. Obviously p1 should be 1 and pm should be n. You should choose the route with minimum total cost. If there are multiple best routes, please choose the one with the smallest lexicographically.
A sequence of integers a is lexicographically smaller than a sequence of b if there exists such index j that ai=bi for all i < j, but aj < bj.

Sample Input

1
3
0 0
3 0
4 0

Sample Output

1 2 3

题目意思

平面有n个点，从1到n编号，现在开飞船从一个点到下一个点。给出你每个带你的坐标，要从 i 点到 j 点要求 xi < xj。飞船消耗的能量就是 xi * yj - xj * yi，消耗值可以为负数。现在问你从第一个点到第n个点的最小消耗情况下输出飞船经过的点的编号，按照字典序排列。

解题思路

看题意可以知道求两点之间的叉乘，并且消耗值可能为负数，所以我们就可以想到凸包，建立一个逆凸包，那么在凸包边上的点根据叉乘和小的按字典序输出即可。

代码部分

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e5+7;
int qu[maxn],mn[maxn];///qu数组用于存储点的下标
struct node
{
    int x,y,id;
    bool operator<(const node &p)const///排序
    {
        if(x!=p.x) return x<p.x;
        if(y!=p.y) return y>p.y;
        return id<p.id;
    }
}pt[maxn];
ll get(int x,int y,int z)///求解xi*yj-xj*yi
{
    int ax=pt[y].x-pt[x].x;
    int ay=pt[y].y-pt[x].y;
    int bx=pt[z].x-pt[y].x;
    int by=pt[z].y-pt[y].y;
    return 1LL*ax*by-1LL*ay*bx;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&pt[i].x,&pt[i].y);
        }
        for(int i=1; i<=n; i++)
        {
            pt[i].id=i;///编号
        }
        sort(pt+1,pt+n+1);
        int now=0;///记录加入凸包的点的个数
        qu[0]=1;///凸包的顶点
        for(int i=2; i<=n; i++)///求解上凸包
        {
            if(pt[i].x==pt[i-1].x)
                continue;
            while(now&&get(qu[now-1],qu[now],i)>0)
                now--;
            qu[++now]=i;
        }
        int l=0,r;
        printf("1");
        while(l<now)
        {
            for(r=l+1; r<=now; r++)
            {
                if(get(qu[l],qu[l+1],qu[r])!=0)///判断是否存在共线
                    break;
            }
            mn[r]=1e9;
            for(int i=r-1; i>=l; i--)
            {
                mn[i]=min(pt[qu[i]].id,mn[i+1]);
            }
            for(int i=l+1; i<=r-1; i++)
            {
                if(mn[i]==pt[qu[i]].id)
                    printf(" %d",pt[qu[i]].id);
            }
            l=r-1;
        }
        cout<<endl;
    }
    return 0;
}