CC

自然万物都趋向从有序变得无序

0%

HDU 6325 Interstellar Travel(凸包)

发表于 更新于 分类于 Valine：

题目链接

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Total Submission(s): 446 Accepted Submission(s): 91

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

Source

2018 Multi-University Training Contest 3

题意:

给定n个点的坐标，要从第一个点走到第n个点，从第i个点走到第j个点的消耗是 x[i] * y[j] - x[j] * y[i],求最小的消耗

思路:

官方题解：

显然坐标相同的点里只保留编号最小的点最优。
将起点到终点的路径补全为终点往下走到无穷远处,再往左
走到起点正下方,再往上回到起点。
任意路径中回到起点部分的代价相同,观察代价和的几何意
义,就是走过部分的面积的相反数。
代价和最小等价于面积最大,故一定是沿着上凸壳行走。
显然起点、终点、凸壳的拐点必须要作为降落点。
对于共线的点 a 1 , a 2 , …, a m ,若一个点 i 的编号是 [i, m] 中最
小的,那么在此处降落可以最小化字典序。
时间复杂度 O(n log n)。

显然我们只需要套一个凸包的板子，套用graham()求凸包的方法;不过不能直接用，需要做一些改变，对于坐标相同的点，我们应该保留编号最小的那个，才能使得字典序最小，而且我们要保留凸包中那些共线的点，因为我们在求凸包的时候，因为对于一堆共线 的点，我们在他们中编号最小的地方降落一定是最优的。

代码:

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
/*************************************************************************
    > File Name: HDU6325.cpp
    > Author: wood
    > Mail: cbcruel@gmail.com
    > Created Time: 2018年07月30日 星期一 20时21分00秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<ctime>
#include<string>

using namespace std;
typedef long long  LL;
typedef long long ll;
const LL eps = 0;
const double C = 0.57721566490153286060651209;
const LL pi = acos(-1.0);
const int maxn = 2e5+10;
const int mod = 1e9 + 7;
const LL INF = 1e18;
#define sqr(x) (x)*(x)

LL dcmp(LL x){
    return x;
}

struct point{
    LL x, y;
    int id;
    point(LL _x = 0, LL _y = 0){
        x = _x; y = _y;

    }
    point operator + (const point &q){
        return point(x+q.x, y+q.y);
    }

    point operator - (const point &q){
        return point(x-q.x, y-q.y);
    }

    bool operator < (const point &q){
        if(x == q.x) return y < q.y;
        return x < q.x;
    }

    bool operator == (const  point &q){
        return dcmp(x-q.x) == 0 && dcmp(y -q.y) == 0;
    }
};

LL dot(point p, point q){
    return p.x*q.x + p.y*q.y;
}

LL det(point p, point q){
    return p.x*q.y - p.y*q.x;
}

LL cross(point p, point q){
    return det(p, q);
}

LL cross(point p1, point p2, point q1, point q2){
    return det(p1-p2,q1-q2);
}

LL dis(point p, point q){
    return sqrt(sqr(p.x-q.x) + sqr(p.y-q.y));
}

LL dis2(point p, point q){
    return sqr(p.x-q.x) + sqr(p.y-q.y);
}

bool cmp(const point &p, const point &q){
    if(p.x != q.x) return p.x < q.x;
    if(p.y != q.y) return p.y < q.y;
    return p.id < q.id;
}



point p[maxn], q[maxn];
int ans[maxn], top, n;

 void graham()
 {
     sort(p+1,p+n+1, cmp);
     for(int i=1;i<=n;i++)
     {
         if(i > 1&& dcmp(p[i].x- p[i-1].x) == 0 && p[i].y == p[i-1].y) continue;
         while(top > 1 && dcmp(cross(p[i], q[top], q[top],q[top-1])) < 0) top--;
         q[++top]=p[i];
     }
 }

bool vis[maxn];
int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        top = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%lld %lld", &p[i].x, &p[i].y), p[i].id = i;
        graham();
        memset(vis, 0, sizeof vis);
        vis[1] = vis[top] = 1;
        for(int i = 2; i < top; ++i)
            if(dcmp(cross(q[i]-q[i-1], q[i+1]-q[i])))
                vis[i] = 1;
        for(int i = top; i > 0; --i)
            if(vis[i])
                ans[i] = q[i].id;
            else ans[i] = min(ans[i+1],q[i].id);
        for(int i = 1; i < top; ++i)
            if(ans[i] == q[i].id)
                printf("%d ", ans[i]);
        printf("%d\n",ans[top]);
    }return 0;
}