学步园

每次选择向左偏移角度最小的下一个点即可。或者说左边点最多的点。

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