Space Ant---poj1696（极角排序）

题目链接：http://poj.org/problem?id=1696

题意：给你n个点，然后我们用一条线把它们连起来，形成螺旋状；

首先找到左下方的一个点作为起点，然后以它为原点进行极角排序，找到极角最小的那个点，如果又多个选距离近的，每次都这样循环找n个点即可;

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <string.h>

using namespace std;

typedef long long LL;

const double eps = 1e-;

const int N = ;

struct point

{

    int x, y, Id;

    point(){}

    point(int x, int y) : x(x), y(y) {}

    point operator - (const point &b)const

    {

        return point(x-b.x, y-b.y);

    }

    int operator ^ (const point &b)const

    {

        return x*b.y - b.x*y;

    }

};

int dist(point a, point b)

{

    return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);

}

int start, n;

point p[N];

bool cmp(point a, point b)

{

    int k = (a-p[start])^(b-p[start]);

    if(k == )

        return dist(p[start], a)<dist(p[start], b);

    return k>;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        for(int i=; i<n; i++)

        {

            scanf("%d %d %d", &p[i].Id, &p[i].x, &p[i].y);

            if(p[i].y < p[].y || (p[i].y==p[].y && p[].x>p[i].x))

                swap(p[i], p[]);

        }

        start = ;

        for(int i=; i<n; i++)

        {

            sort(p+i, p+n, cmp);

            start ++;

        }

        printf("%d", n);

        for(int i=; i<n; i++)

            printf(" %d", p[i].Id);

        printf("\n");

    }

    return ;

}