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;
}
推荐阅读
-
HDU-1392 Surround the Trees(凸包+周长)
-
2018 Multi-University Training Contest 3 1007 / hdu6325 Problem G. Interstellar Travel 凸包
-
2018 Multi-University Training Contest 3 &&HDU6325 Interstellar Travel【凸包】
-
2018多校第3场 G题 && HDU6325 Problem G. Interstellar Travel
-
HDU 6325 Interstellar Travel(凸包)
-
HDU 6325 Problem G. Interstellar Travel(上凸包)
-
HDU 6325 Interstellar Travel 【凸包+单调栈】
-
hdu6325 Problem G. Interstellar Travel
-
HDU 6325 Interstellar Travel【凸包】
-
hdu 6325 Interstellar Travel (凸包)