題意:
給你n個點,第一個點一定是(0,0)，最后一個點縱坐標yn一定是0，中間的點的橫坐標一定都是在(0,xn)之間的
?然后從第一個點開始飛行，每次飛到下一個點j，你花費的價值就是xi*yj-xj*yi，并且這里每一次飛行必須滿足xi<xj
讓你求出你所花費的最小的價值(可以為負)下，飛行的路徑，如果有多種情況，輸出路徑字典序最小的那個
顯然坐標相同的點里只保留編號最小的點最優。這里是因為題目嚴格要求xi<xj，所以不可能在原地飛行。
將起點到終點的路徑補全為終點往下走到無窮遠處，再往左走到起點正下方，再往上回到起點。任意路徑中回到起點部分的代價相同，觀察代價和的幾何意義，就是走過部分的面積的相反數。代價和最小等價于面積最大，故一定是沿著上凸殼行走。
顯然起點、終點、凸殼的拐點必須要作為降落點。對于共線的點a?1??,a?2??,...,a?m??，若一個點ii的編號是[i,m]中最小的，那么在此處降落可以最小化字典序。
#include<bits/stdc++.h> using namespace std; const int mx = 2e5 + 10; typedef long long ll; int n,m,ans[mx],top,ma; struct node {int x,y;int pos; }s[mx],tubeg[mx],w; bool vis[mx]; ll judge(node p1,node p2,node p0)//面積公式判斷正負值 {ll ans = 1ll*(p1.x-p0.x)*(p2.y-p0.y) - 1ll*(p2.x-p0.x)*(p1.y-p0.y);return ans; } bool cmp(node a,node b) {ll c = judge(w,b,a);//極角排序,同角度按距離從小到大排 if(b.x==a.x&&b.y==a.y) return a.pos > b.pos;if(!c) return pow(a.x-w.x,2)+pow(a.y-w.y,2) < pow(b.x-w.x,2)+pow(b.y-w.y,2);return c > 0; } void Graham() {tubeg[0] = s[0],tubeg[1] = s[1];top = 2;for(int i=2;i<n;i++){while(top>1&&judge(tubeg[top-2],s[i],tubeg[top-1])<=0){if(judge(tubeg[top-2],s[i],tubeg[top-1])<0||tubeg[top-1].pos>s[i].pos) top--;else break;}tubeg[top++] = s[i];}for(int i=0;i<top;i++) printf("%d%c",tubeg[i].pos+1,i==top-1?'\n':' '); } int main() {int t;scanf("%d",&t);while(t--){scanf("%d",&n);memset(vis,0,sizeof(vis));for(int i=0;i<n;i++){scanf("%d%d",&s[i].x,&s[i].y);s[i].pos = i; }w = s[0];sort(s+1,s+n,cmp);Graham();}return 0; }
?
