没看题解，搜了一下都是什么叉积凸包，根本没有必要用吧。。
显然这个题我们找夹角就可以了，根据高中的公式 a·b=|a|*|b|*cos<a,b>
所以用点积找一个 cos<a,b> 最小的角就可以了。
一发ac稳得一批
1 #include <cstdio> 2 #include <cmath> 3 #include <iostream> 4 #include <vector> 5 #include <algorithm> 6 #include <cstring> 7 using namespace std; 8 typedef double db; 9 const db eps=1e-6; 10 const db pi=acos(-1); 11 int sign(db k){ 12 if (k>eps) return 1; else if (k<-eps) return -1; return 0; 13 } 14 int cmp(db k1,db k2){return sign(k1-k2);} 15 struct point{ 16 db x,y;int id; 17 point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};} 18 point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};} 19 point operator * (db k1) const{return (point){x*k1,y*k1};} 20 point operator / (db k1) const{return (point){x/k1,y/k1};} 21 db abs(){return sqrt(x*x+y*y);} 22 }; 23 db cross(point k1,point k2){ return k1.x*k2.y-k2.x*k1.y;} 24 db dot(point k1,point k2){ return k1.x*k2.x+k1.y*k2.y;} 25 int t,n; 26 point p[55]; 27 bool cmp2(point a,point b){ 28 return a.y<b.y; 29 } 30 vector <point>ans; 31 int vis[55]; 32 int main(){ 33 ios::sync_with_stdio(false); 34 cin>>t; 35 while (t--){ 36 cin>>n; 37 for(int i=1;i<=n;i++){ 38 cin>>p[i].id>>p[i].x>>p[i].y; 39 } 40 sort(p+1,p+1+n,cmp2); 41 p[0].x=0,p[0].y=p[1].y; 42 ans.push_back(p[0]); 43 ans.push_back(p[1]); 44 vis[1]=1; 45 for(int i=2;i<=n;i++){ 46 int m=ans.size(); 47 point now = ans[m-1]-ans[m-2];//之前的向量，找最小左偏。 48 49 int id=-1; 50 db mn=-2; 51 for(int j=1;j<=n;j++){ 52 if(vis[j])continue; 53 point tmp = p[j]-ans[m-1]; 54 db c = dot(tmp,now)/tmp.abs()/now.abs(); 55 if(cmp(c,mn)==1){ 56 //printf("%lf %lf ",tmp.x,tmp.y); 57 mn = c; 58 id=j; 59 } 60 } 61 if(id==-1)break; 62 else { 63 ans.push_back(p[id]); 64 vis[id]=1; 65 } 66 } 67 cout<<n<<" "; 68 for(int i=1;i<ans.size();i++){ 69 cout<<ans[i].id; 70 if(i!=ans.size()-1) 71 cout<<' '; 72 } 73 cout<<endl; 74 ans.clear(); 75 memset(vis,0, sizeof(vis)); 76 } 77 }