45
POJ 1696 向量叉积
题意：给一个蚂蚁只能向左转，不能穿过以前走过的路径。求经过点的顺序。
在纸上画一下就能发现每个点都可以走到所以只需要求路径就可以了。利用一个标记数组记录走过的点，然后利用叉积寻找一点在剩余点的右侧就可以了。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct point
{
int x,y,num;
};
int Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
int main()
{
int t,n,m;
point data[60],now;
bool map[60];
scanf("%d",&t);
while(t--)
{
memset(map,0,sizeof(map));
scanf("%d",&n),m=n;
int miny=9999;
for(int i=1; i<=n; i++)
scanf("%d%d%d",&data[i].num,&data[i].x,&data[i].y),miny=min(miny,data[i].y);
now.x=0,now.y=miny;
printf("%d",n);
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
{
int sum=0;
for(int j=1; j<=n; j++)
if(!map[j]&&Direction(now,data[j],data[i])<=0&&j!=i)
sum++;
if(sum==n-k&&!map[i])
{
now=data[i];
map[now.num]=1;
printf(" %d",now.num);
break;
}
}
printf("\n");
}
return 0;
}
最后更新：2017-04-03 20:51:31