# 原始题目

## 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

chendu

# 题目大意

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

# 解题思路

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

# 收获与反思

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