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
题目大意：给出n个点，从1到n，每次走只能到横坐标比当前点大的点，花费为两点坐标之间的叉积，要求找出花费最小的路线，以字典序依次输出路线上的点。
思路：题目太绕，数学又不怎么好，没看出是求上凸包问题。赛后看了题解，，，emmm好像我也能做呀.....
推导：
代价和与面积为什么是相反数(这是个结论)：代价和是邻点叉积和(向量积和)，任意多边形面积的公式为：（详细推导过程请自己尝试或百度）
所以这个题就变成了一个求n个点所构成的上凸包，并按照字典序输出。
取凸包模板的上凸包部分与斜率判断，判点后将点存在单调栈里。(存的点本来就是单调的....就是按顺序存起来)
代码如下(700ms)：
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<string> #include<cmath> #include<stack> #include<vector> using namespace std; const int maxn=200010; typedef long long ll; struct node{ int id;//点序 ll x,y;//坐标 }a[maxn]; int t,n,s[maxn]; bool cmp(const node &a,const node &b)//若重点，取序号靠前的点，若横坐标相同，取纵坐标较大的上界点 { if(a.x==b.x) { if(a.y==b.y) return a.id<b.id; return a.y>b.y; } return a.x<b.x; } bool fun(int i,int j,int k) { if((a[k].y-a[i].y)*(a[j].x-a[i].x)==(a[j].y-a[i].y)*(a[k].x-a[i].x))//斜率比较 return a[k].id<a[j].id;///斜率相同时，看编号是不是满足字典序小的 return (a[k].y-a[i].y)*(a[j].x-a[i].x)>(a[j].y-a[i].y)*(a[k].x-a[i].x);// } int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld",&a[i].x,&a[i].y); a[i].id=i; } int top=0; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { if(i!=1&&a[i].x==a[i-1].x&&a[i].y==a[i-1].y)//重合的点就不要了 continue; while(top>1&&fun(s[top-1],s[top],i)!=0)//斜率判断，返回的是斜率更大的点(上凸包点维护) top--; s[++top]=i; } for(int i=1;i<top;i++) printf("%d ",a[s[i]].id); printf("%d\n",a[s[top]].id); } return 0; }
