HDU-6325 Interstellar Travel(几何...上凸包)
Interstellar Travel
Time Limit: 4000/2000 MS (Java/Others)
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
题意:从X最小都到X最大,每次只能往x增大的方向走,花费为xi*yj-xj*yi,为负数则赚了.问最小花费选的点且字典序最小.
思路:首先我们想每个x只能选一次,重合点也只能选一个.其实就是i向量与j向量叉乘,我们想尽量为负数,j在i的顺时针方向则为负,反之则为正,所以我们想要得到一个上凸包~~几个点x相同当然要选y比较大的那个,这也就决定了我们的排序顺序.
最后还要保证字典序最小,这里还要说一点,求上凸包的过程下面我写的那个函数,< 则会留下在同一条直线的几个点,<= 则同一条直线只留两个端点,假如我们同一条直线的几个点都留下了,则最后我们还要看一看那些留下,哪些删去.端点必须留下,也就是说直线上可使字典序变小的点我们也留下~
代码:
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
map<int,int>::iterator it;
struct node
{
int x,y;
int pos;
node(){}
node(int x,int y):x(x),y(y){pos = 0;}
friend node operator - (node A,node B)
{
return node(A.x-B.x,A.y-B.y);
}
} p[maxn],q[maxn];
int n,cnt;
int ans[maxn];
bool vis[maxn];
bool cmp(node x,node y)//注意排序规则
{
if(x.x != y.x) return x.x< y.x;
if(x.y != y.y)return x.y> y.y;
return x.pos< y.pos;
}
ll cross(node A,node B)//叉乘
{
return 1ll*A.x*B.y-1ll*A.y*B.x;
}
bool judge(node A,node B,node C)//判断是否共线
{
return cross(B-A,C-A)!= 0;
}
void ConvexHull(node p[],node q[])//求上凸包
{
cnt = 0;
for(int i=1;i<=n;i++)
{
if(i> 1&&p[i].x==p[i-1].x)continue;
while(cnt>=2&&1ll*(q[cnt].y-q[cnt-1].y)*(p[i].x-q[cnt].x)< 1ll*(q[cnt].x-q[cnt-1].x)*(p[i].y-q[cnt].y))cnt--;
q[++cnt]=p[i];
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
mem(vis,0);
scanf("%d",&n);
for(int i = 1;i<= n;i++)
scanf("%d %d",&p[i].x,&p[i].y),p[i].pos = i;
sort(p+1,p+n+1,cmp);
ConvexHull(p,q);
vis[1] = vis[cnt] = 1;
for(int i = 2;i< cnt;i++)
if(judge(q[i-1],q[i],q[i+1])) vis[i] = 1;//先只留端点
for(int i = cnt;i>= 1;i--)//看看非端点是否可是字典序变小
if(vis[i]) ans[i] = q[i].pos;
else ans[i] = min(q[i].pos,ans[i+1]);
for(int i = 1;i< cnt;i++)
if(ans[i] == q[i].pos) printf("%d ",ans[i]);
printf("%d\n",ans[cnt]);
}
return 0;
}
推荐阅读
-
2018 Multi-University Training Contest 3 1007 / hdu6325 Problem G. Interstellar Travel 凸包
-
2018 Multi-University Training Contest 3 &&HDU6325 Interstellar Travel【凸包】
-
HDU 6325 Interstellar Travel(凸包)
-
HDU 6325 Problem G. Interstellar Travel(上凸包)
-
HDU 6325 Interstellar Travel 【凸包+单调栈】
-
HDU 6325 Interstellar Travel【凸包】
-
hdu 6325 Interstellar Travel (凸包)
-
HDU-6325 Interstellar Travel(几何...上凸包)