每次选择向左偏移角度最小的下一个点即可。或者说左边点最多的点。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <map>
#include <sstream>
#include <queue>
#include <vector>
#define MAXN 100005
#define MAXM 211111
#define eps 1e-8
#define INF 500000001
using namespace std;
inline int dblcmp(double d)
{if(fabs(d) < eps) return 0;return d > eps ? 1 : -1;
}
struct point
{double x, y;point(){}point(double _x, double _y): x(_x), y(_y) {}void input(){scanf("%lf%lf", &x, &y);}bool operator ==(point a)const{return dblcmp(a.x - x) == 0 && dblcmp(a.y - y) == 0;}point sub(point p){return point(x - p.x, y - p.y);}double dot(point p){return x * p.x + y * p.y;}double det(point p){return x * p.y - y * p.x;}double distance(point p){return hypot(x - p.x, y - p.y);}
}p[555];
int vis[555];
int n;
vector<int>ans;
int getcount(point a, int id)
{int cnt = 0;for(int i = 1; i <= n; i++){if(vis[i] || id == i) continue;point tmp = p[i].sub(p[id]);if(dblcmp(a.det(tmp)) >= 0) cnt++;}return cnt;
}
void disable(point a, int id)
{for(int i = 1; i <= n; i++){if(vis[i]) continue;point tmp = p[i].sub(p[id]);if(dblcmp(a.det(tmp)) < 0) vis[i] = 1;}
}
int main()
{int T;scanf("%d", &T);while(T--){scanf("%d", &n);p[0] = point(0, 0);int pre = 0, now = -1, id;for(int i = 1; i <= n; i++){scanf("%d", &id); p[i].input();if(now == -1 || p[i].y < p[now].y) now = i;}memset(vis, 0, sizeof(vis));ans.clear();ans.push_back(now);vis[now] = 1;while(true){int nxt = -1, cnt = 0;for(int i = 1; i <= n; i++)if(!vis[i]){point x = p[i].sub(p[now]);int num = getcount(x, i);if(num >= cnt)nxt = i, cnt = num;}if(nxt == -1) break;vis[nxt] = 1;point tmp = p[nxt].sub(p[now]);disable(tmp, nxt);ans.push_back(nxt);pre = now;now = nxt;}printf("%d", ans.size());for(int i = 0; i < ans.size(); i++) printf(" %d", ans[i]);printf("\n");}return 0;
}