欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

hdu 6325 Interstellar Travel (凸包)

程序员文章站 2022-03-30 08:33:45
...

http://acm.hdu.edu.cn/showproblem.php?pid=6325

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

思路:因为凸包是求逆时针的时候面积包住所有点的面积最大,那么我们题目这样是顺时针,相反的就是面积最小,所以这题就是求顺时针的凸包,那肯定就包括起点、终点、凸包的拐点了,只要把上凸包求出来就好。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
struct node
{
    ll x,y;
    int id;
}a[N];
int s[N];
bool cmp(node a,node b)
{
    if(a.x==b.x)
    {
        if(a.y==b.y)
        {
            return a.id<b.id;
        }
       return a.y>b.y;
    }
    else return a.x<b.x;
}
bool judge(int x,int y,int z)
{
    if((a[z].y-a[x].y)*(a[y].x-a[x].x)==(a[z].x-a[x].x)*(a[y].y-a[x].y))
        return a[z].id<a[y].id;
    if((a[z].y-a[x].y)*(a[y].x-a[x].x)>(a[z].x-a[x].x)*(a[y].y-a[x].y))
        return true;
    return false;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld%lld",&a[i].x,&a[i].y);
            a[i].id=i;
        }
        sort(a+1,a+1+n,cmp);
        int top=0;
        s[top++]=1;
        for(int i=2;i<=n;i++)
        {
            if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y)
                continue;
            while(top>=2&&judge(s[top-2],s[top-1],i))
                top--;
            s[top++]=i;
        }
        for(int i=0;i<top;i++)
        {
            if(i)printf(" ");
            printf("%d",a[s[i]].id);
        }
        printf("\n");
    }
    return 0;
}