题目大意：给定n个点，然后这只蚂蚁只能向左拐弯而且不能走重复的路线，从最低的点开始走，就是求一个类似蜗牛壳庄的图形，输出走的顺序。其中第一个点是可以最大走的个数，有点求凸包的意思，可以用卷包裹法来求。卷包裹法的意思 就是： 像卷包裹一样，一层一层的找，这个上面讲的比较好http://www.cnblogs.com/Booble/archive/2011/02/28/1967179.html
刚开始写不出代码来的原因就是以为找下一个最优点的时候万一要在这个点的顺时针方向上怎么办，后来想了想根本不可能，因为如果找到当前这个点的话，这个点一定是可以走的最靠外的一个，所以再找下一个的话，一定是在它左侧的。利用叉积来判断线段的相对位置。
我的代码：
/*************************************************************************
> File Name: poj_1696.cpp
> Author: Howe_Young
> Mail: [email protected]
> Created Time: 2015年04月14日 星期二 16时41分10秒
************************************************************************/ #include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#define EPS 1e-8
using namespace std;
const int maxn = ;
struct point{
double x, y;
int num;//定点序号
};
point p[maxn];
bool vis[maxn];//标记是否已经取到
int ans[maxn];//保存取的顺序
int m, n;
int k;
bool cmp(const point p1, const point p2)//排序比较函数，这个题其实不用排序，找到y最小的点那个就行了
{
return (p1.y == p2.y && p1.x < p2.x || p1.y < p2.y);
}
int sgn(double x)
{
if (fabs(x) < EPS)
return ;
return x < ? - : ;
}
double get_direction(point p1, point p2, point p3)//p1p3在p1p2的左侧的时候小于0
{
return (p3.x - p1.x) * (p2.y - p1.y) - (p2.x - p1.x) * (p3.y - p1.y);
}
double get_distance(point p1, point p2)//两点之间的距离
{
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
void jarvis()//卷包裹法
{
memset(vis, false, sizeof(vis));
vis[] = vis[] = true;//其中p[0]是构造出来的，由题意可知，第一个点在y轴上
int optimal, cur = ;//optimal保存最优的(最靠外的)那个点，cur是当前点
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (!vis[j])
{
optimal = j; break;//从待选泽的点中随便找一个点让optimal等于它，因为下面要和其他的点比较
}
}
for (int j = ; j <= n; j++)
{
if (!vis[j] && optimal != j && sgn(get_direction(p[cur], p[j], p[optimal])) < )//这里是没有共线的情况，如果有共线的话必须严格的判断
{
optimal = j;
}
}
vis[optimal] = true;
cur = optimal;
ans[k++] = p[optimal].num;
}
}
int main()
{
//freopen("in.txt", "r", stdin);
scanf("%d", &m);
while (m--)
{
k = ;
memset(ans, , sizeof(ans));
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d %lf %lf", &p[i].num, &p[i].x, &p[i].y);
sort(p + , p + n + , cmp);//排序
p[].num = ; p[].x = ; p[].y = p[].y;//构造第一个点
ans[k++] = p[].num;
jarvis();
printf("%d ", n);
for (int i = ; i < k; i++)
printf("%d ", ans[i]);
puts("");
} return ;
}
其中上面有个步骤是没有严格的判断是否共线的问题，不过也能AC，可能数据比较少把，下面给出严格的判断共线问题的代码
void jarvis()
{
memset(vis, false, sizeof(vis));
vis[] = vis[] = true;
int optimal, cur = ;
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (!vis[j])
{
optimal = j; break;
}
}
for (int j = ; j <= n; j++)
{
if (!vis[j] && optimal != j && sgn(get_direction(p[cur], p[j], p[optimal])) <= )
{
if (sgn(get_direction(p[cur], p[j], p[optimal])) == )//如果共线
{
if (get_distance(p[cur], p[j]) < get_distance(p[cur], p[optimal]))//判断距离小的点是哪个
optimal = j;
}
else
optimal = j;
}
}
vis[optimal] = true;
cur = optimal;
ans[k++] = p[optimal].num;
}
}