题目描述：

一个蚂蚁只能左转和直走，且不能和之前走过的路相交。现在在地图上有n个植物，告诉你每一个的坐标，让你找一条路线，是蚂蚁能够吃掉最多的植物。

解题报告：

每次选点都是使其余所有的点都在最近加入的线段的逆时针方向即可（叉积含义），实际上使可以吃掉所有植物的，也就是总会存在一个符合条件的点。

代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define size 50
struct pint{int id, x, y;}x[size], pre;
bool vst[size];
bool cmp(pint a, pint b)
{
    if (a.y == b.y) return a.x < b.x;
    return a.y < b.y;
}
int t, n, ans[50], cnt;
int CrossProduct(pint p1, pint p2, pint p3)
{
    int temp = (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);
    if (temp < 0) return true;
    else if (temp == 0)
        return !(p3.x >= min(p1.x, p2.x) && p3.x <= max(p1.x, p2.x));
    else return false;
}
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        cnt = 0;
        for(int i = 0; i < n; i++)
            scanf("%d%d%d", &x[i].id, &x[i].x, &x[i].y);
        sort(x, x + n, cmp);
        ans[cnt++] = x[0].id;
        memset(vst, 0, sizeof(vst));
        vst[0] = 1;pre = x[0];
        for(int i = 0; i < n - 1; i++)
            for(int j = 1; j < n; j++)
                if (!vst[j])
                {
                    bool flag = true;
                    for(int k = 1; k < n; k++)
                        if (k != j && !vst[k] && !CrossProduct(pre, x[j], x[k]))
                        {
                            flag = false;
                            break;
                        }
                    if (flag)
                    {
                        vst[j] = 1;
                        pre = x[j];
                        ans[cnt++] = x[j].id;
                        break;
                    }
                }
        printf("%d", cnt);
        for(int i = 0; i < cnt; i++)
            printf(" %d", ans[i]);
        printf("\n");

    }
    return 0;
}