【HDU-6325】解题报告（计算几何，2018杭电多校第三场）

原始题目

Problem G. Interstellar Travel

  • Time Limit: 4000/2000 MS (Java/Others)
  • Memory Limit: 524288/524288 K (Java/Others)
  • Total Submission(s): 638
  • Accepted Submission(s): 137

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\times y\_j-x\_j\times 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.

Input

The first line of the input contains an integer \(T(1\leq T\leq10)\), denoting the number of test cases.

In each test case, there is an integer \(n(2\leq n\leq 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\leq x\_i,y\_i\leq 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\).

Output

For each test case, print a single line containing several distinct integers \(p\_1,p\_2,...,p\_m(1\leq p\_i\leq n)\), denoting the route you chosen is \(p\_1\rightarrow p\_2\rightarrow...\rightarrow p\_{m-1}\rightarrow 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\).

Sample Input

1
3
0 0
3 0
4 0

Sample Output

1 2 3

Source

2018 Multi-University Training Contest 3

Recommend

chendu

题目大意

  • 给了\(n\)个星球的横纵坐标，从第一个星球旅行到第n个星球，消耗的燃料是叉积（可能为负）
  • 已知\(y\_1=y\_n=0,0=x\_1<x\_2,x\_3,...,x\_{n-1}<x\_n\)，每次旅行下一个星球的\(x\)坐标要大于上一个星球。
  • 求消耗燃料的最小值，输出字典序最小的满足条件的访问顺序。

解题思路

  • 即求从第一个点到第n个星球的上半凸包（有向面积最小，负最大）
  • 三点共线和同点的时候要满足字典序最小的要求。 共线时判断中间点字典序是不是小于后点，共点时保留序列最小的。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size()) 
const int maxn=2e5+5;
const double eps=1e-9;
typedef long long ll;
ll n,cnt;
//有的命名为sgn函数，高精度符号判断 
ll dcmp(double x){
	//相等函数判断，减少精度问题 
	if(fabs(x)<eps) return 0;
	else return x<0?-1:1;
}

//点的定义 
class Point{
	public:
	ll x,y;
	Point (ll x=0,double y=0):x(x),y(y){} //构造函数，方便代码的编写 
}; 

typedef Point Vector;// 从程序实现上，Vector只是Point的别名

//运算符重载 
//向量+向量=向量，点+向量=点
Vector operator + (const Vector &A,const Vector &B) { return Vector(A.x+B.x,A.y+B.y); }
//向量-向量=向量，点-向量-点 
Vector operator - (const Vector &A,const Vector &B) { return Vector(A.x-B.x,A.y-B.y); }
//向量*数=向量 （数乘） 
Vector operator * (const Vector &A,double p) { return Vector(A.x*p,A.y*p); }
//向量/数=向量 （数除） 
Vector operator / (const Vector &A,double p) { return Vector(A.x/p,A.y/p); }
//向量（点乘）向量=数  （点乘）
double operator * (const Vector &A,const Vector &B) { return A.x*B.x+A.y*B.y; }
double dot(const Vector &A,const Vector &B){ return A.x*B.x+A.y*B.y; }
//向量（叉乘）向量=向量 （叉乘） 
double operator ^ (const Vector &A,const Vector &B){ return A.x*B.y-A.y*B.x; }
ll cross(const Vector &A,const Vector &B){ return A.x*B.y-A.y*B.x; }
//计算向量模长 
double abs(const Vector &A){ return sqrt(dot(A,A));}
//计算平行四边形方向面积
double area2(const Point &A,const Point &B,const Point &C){ return cross(B-A,C-A) ;} 
 
//按x值递增排序 
bool operator < (const Point &A,const Point &B) { return A.x==B.x?A.y<B.y:A.x<B.x; } 

//判定两个点是否相同，用到dcmp精度判定 
bool operator == (const Point &A,const Point &B) { return dcmp(A.x-B.x)==0&& dcmp(A.y-B.y)==0; } 

//向量旋转
Vector rotate(Vector A,double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));}
//计算单位法线，左转90
Vector normal(Vector A){
	double l=abs(A);
	return Vector(-A.y/l,A.x/l);
} 

//线段定义 
class Line {
	public:
		Point s,e;
		Line(){}
		Line(Point _s,Point _e){
			s=_s;e=_e;
		}
		
}line[maxn];
//判断两线段是否相交 
bool inter(Line l1,Line l2){
//	cout<<"L1  "<<l1.e.x<<","<<l1.e.y<<"   "<<l1.s.x<<","<<l1.s.y<<endl;
//	cout<<"L2  "<<l2.e.x<<","<<l2.e.y<<"   "<<l2.s.x<<","<<l2.s.y<<endl;
	return (
		//根据题目要求端点相交是否算作相交来决定大于等于和小于等于 
		//排斥实验 
		max(l1.s.x,l1.e.x)>=min(l2.s.x,l2.e.x) &&
		max(l2.s.x,l2.e.x)>=min(l1.s.x,l1.e.x) &&
		max(l1.s.y,l1.e.y)>=min(l2.s.y,l2.e.y) &&
		max(l2.s.y,l2.e.y)>=min(l1.s.y,l1.e.y) &&
		//跨立实验 
		dcmp((l2.s-l1.s)^(l1.s-l1.e))*dcmp((l2.e-l1.s)^(l1.s-l1.e))<0 &&
		dcmp((l1.s-l2.s)^(l2.s-l2.e))*dcmp((l1.e-l2.s)^(l2.s-l2.e))<0
	) ;
}
bool inter(Point a1,Point a2,Point b1,Point b2){
	Line l1(a1,a2),l2(b1,b2);
	return inter(l1,l2);
}

//求两直线交点
Point getinter(Line l1,Line l2){
	Vector v=l1.s-l1.e;
	Vector w=l2.s-l2.e;
	Vector u=l1.e-l2.e;
	double t=cross(w,u)/cross(v,w);
	return l1.e+v*t;
} 
Point getinter(Point a1,Point a2,Point b1,Point b2){
	Line l1(a1,a2);
	Line l2(b1,b2);
	return getinter(l1,l2);
}


//判定点和线段的关系，
//0:不在线段所在直线上
//1:在线段内（不含端点） 
//2:在线段端点
//3:在线段两侧的射线上 
ll  online(Point a,Line l){
	if(dcmp(cross(l.s-a,l.e-a))!=0) return 0;
	double pans=dcmp(dot(l.s-a,l.e-a));
//	cout<<(l.s-a).x<<","<<(l.s-a).y<<"   "<<(l.e-a).x<<","<<(l.e-a).y<<endl;
	if(pans<0) return 1;
	else if(pans==0) return 2;
	else if(pans>0) return 3;
}
ll online(Point a,Point b1,Point b2){
	Line l(b1,b2);
	return online(a,l);
}


class node{
	public:
		ll index;
		Point p;
} point[maxn],ans[maxn],pre[maxn];
bool cmp(node a, node b){
	if(a.p.x==b.p.x){
		if(a.p.y==b.p.y) return a.index>b.index;
		return a.p.y<b.p.y;
	}
	else {
		return a.p.x<b.p.x;
	}
}


ll ConvexHull()
{
	ll flag=0;
	ll m=0;
	for(ll i=1;i<=cnt;i++){
		if(!flag && point[i].index!=1) continue;
		if(point[i].index==1){
			flag=1;
		}

		while(m>1 && cross(ans[m-1].p-ans[m-2].p,point[i].p-ans[m-2].p)>=0) {
			if(m>1 && cross(ans[m-1].p-ans[m-2].p,point[i].p-ans[m-2].p)==0){
				//判断字典序
				if(point[i].index<ans[m-1].index) m--;
				else break;
			}
			else if(m>1 && cross(ans[m-1].p-ans[m-2].p,point[i].p-ans[m-2].p)>0){
				m--;
			}
		}
		ans[m].p=point[i].p;
		ans[m].index=point[i].index;
//		cout<<m<<"  ans.p=("<<ans[m].p.x<<","<<ans[m].p.y<<"   index="<<ans[m].index<<endl;
//		cout<<"$$$$"<<ans[m].index<<"     "<<n<<"$$$$"<<endl; 
		m++;
		if(ans[m-1].index==n) break;
//		cout<<m<<"  ans.p=("<<ans[m].p.x<<","<<ans[m].p.y<<"   index="<<ans[m].index<<endl;
		
	}
	return m;
}


int main(){
	ios::sync_with_stdio(false);
	ll t;
	cin>>t;
	while(t--){
		cin>>n;
		cnt=0;
		rep(i,1,n+1){
			cin>>pre[i].p.x>>pre[i].p.y;
			pre[i].index=i;
		}
		sort(pre+1,pre+n+1,cmp);

		rep(i,1,n+1){
			if(i==1) point[++cnt]=pre[i];
			else if(pre[i].p.x==point[cnt].p.x) point[cnt]=pre[i];
			else point[++cnt]=pre[i];
		}

		ll len=ConvexHull();
		rep(i,0,len){
			if(i==0) cout<<ans[i].index;
			else cout<<" "<<ans[i].index;
		}
		cout<<endl;
	}
}
 
//1
//7
//1 1
//3 5
//3 1
//1 3
//2 4
//7 2
//9 1

//2 
//13
//1 0 
//3 5
//3 1
//2 4
//5 3
//4 6
//2 4
//7 2
//6 13
//9 1
//3 0
//10 1
//11 0

收获与反思

  • 注意long long
  • 可能出现共点情况，三点共线情况，都要考虑字典序的要求