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