学步园

题目：题目链接

题意：找逆时针螺旋线最多能连几个点

分析：贪心使用一些几何上的极角排序，凸包的应用，每次都连最外面的点即可。每次找到一个当前点curp，除了第一

次是对数组按纵坐标排序得出外，剩下的均按极角排序。使用一个ans数组记录链接的每一个点：

代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <map>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <functional>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <stack>
#include <ctime>
#include <list>
#define INF 0x7fffffff
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
struct Point
{
    int x, y;
    int index;
};

Point curp;
int Cross(const Point &o, const Point &a, const Point &b)
{
    return (a.x - o.x)*(b.y - o.y) - (b.x - o.x)*(a.y - o.y);
}

bool CmpByy(const Point &a, const Point &b)
{
    return a.y < b.y;
}

double dis(const Point &a, const Point &b)
{
    return sqrt(double((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y)));
}

bool CmpBYAngle(const Point &a, const Point &b)
{
    int res = Cross(curp, a, b);
    if(res > 0)
        return true;
    else if(res < 0)
        return false;
    else
    {
        double dis1 = dis(a, curp);
        double dis2 = dis(b, curp);
        if(dis1 < dis2)
            return true;
        else
            return false;
    }
}

Point point[55];
int main()
{
    int M;
    scanf("%d", &M);
    int n;
    while(M--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d", &point[i].index, &point[i].x, &point[i].y);
        sort(point, point+n, CmpByy);
        curp = point[0];
        int ans[1000];
        mem(ans, 0);
        int cnt = 0;
        int pos = 0;
        ans[pos++] = curp.index;
        //cout << " " << curp.index ;
        for(int i = 1; i < n; i++)
        {
            sort(point+i,point+n,CmpBYAngle);
            curp = point[i];
            ans[pos++] = curp.index;
            cnt++;
            //cout << " " << curp.index;
        }
        printf("%d", pos);
        for(int i = 0; i < pos; ++i)
            printf(" %d", ans[i]);
        printf("\n");

    }
    return 0;
}