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

HDU-6325 Interstellar Travel(几何...上凸包)

程序员文章站 2022-03-02 10:21:30
...

                                                                                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;
}

 

相关标签: 几何