链接:http://acm.hdu.edu.cn/showproblem.php?pid=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 (x
i
,y
i
)
.
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 x
i
<x
j![]()
, which will cost his spaceship x
i
×y
j
−x
j
×y
i![]()
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.
Little Q knows the position of n
Little Q plans to start his journey at the 1
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 x
i
,y
i
(0≤x
i
,y
i
≤10
9
)
, 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 y
1
=y
n
=0,0=x
1
<x
2
,x
3
,...,x
n−1
<x
n![]()
.
In each test case, there is an integer n(2≤n≤200000)
For the next n
Output
For each test case, print a single line containing several distinct integers p
1
,p
2
,...,p
m
(1≤p
i
≤n)
, denoting the route you chosen is p
1
→p
2
→...→p
m−1
→p
m![]()
. Obviously p
1![]()
should be 1
and p
m![]()
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 a
i
=b
i![]()
for all i<j
, but a
j
<b
j![]()
.
A sequence of integers a
Sample Input
1
3
0 0
3 0
4 0
Sample Output
1 2 3
Source
Recommend
chendu
题解:WA了无数发,忘了一句话,“有的星球由于太近可以认为坐标相同,但输出的时候应该输出编号小的”,后来重读了题目,家里个条件就过了;
这个题目可以转化为凸包问题,只求上凸包,求上凸包时注意排除横坐标相同的点,只取纵坐标大的点,重要的一点:对于纵坐标相同而横坐标不同的点,我们需要判断中间点的编号是否比下一个点大,因为按字典序输出,故如果大于则去掉该点,小于等于则保留,注意细节;
参考代码:
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn=2e5+10; LL vis[maxn],T,n; LL num[maxn]; struct Point{ LL x,y; LL id; Point(double xx=0,double yy=0) : x(xx),y(yy) {} } p[maxn],ch[maxn]; typedef Point Vector; Vector operator + (Vector a,Vector b) { return Vector(a.x+b.x,a.y+b.y); } Vector operator - (Vector a,Vector b) { return Vector(a.x-b.x,a.y-b.y); } Vector operator * (Vector a,Vector b) { return Vector(a.x*b.x,a.y*b.y); } Vector operator / (Vector a,Vector b) { return Vector(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? a.id<b.id : a.y>b.y) : a.x<b.x ; } LL Cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; } void ConvexHull() { LL m=0; memset(vis,0,sizeof vis); for(int i=1;i<=n;i++) { if(i>1 && p[i].x == p[i-1].x) continue; while(m>1 && Cross(ch[m]-ch[m-1],p[i]-ch[m])>0) m--; ch[++m]=p[i]; } vis[1]=vis[m]=1; for(int i=2;i<m;i++) if(Cross(ch[i+1]-ch[i],ch[i]-ch[i-1])!=0) vis[i]=1; for(int i=m;i>0;i--) { if(vis[i]) num[i]=ch[i].id; else num[i]=min(num[i+1],ch[i].id); } for(int i=1;i<m;i++) if(num[i]==ch[i].id) printf("%lld ",num[i]); printf("%lld\n",num[m]); } int main() { scanf("%lld",&T); while(T--) { scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y),p[i].id=i; sort(p+1,p+n+1); ConvexHull(); } return 0; }