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;
}



目录
相关文章
|
1月前
acwing 173 矩阵距离
acwing 173 矩阵距离
11 0
|
6月前
矩阵 螺旋矩阵
矩阵 螺旋矩阵
49 2
|
6月前
leetcode-542:01 矩阵
leetcode-542:01 矩阵
41 0
|
算法 C++
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
Acwing 平方矩阵 C++
Acwing 平方矩阵 C++
129 0
Acwing 平方矩阵 C++
AcWing 754. 平方矩阵 II
AcWing 754. 平方矩阵 II
96 0
AcWing 754. 平方矩阵 II
AcWing 753. 平方矩阵 I
AcWing 753. 平方矩阵 I
72 0
AcWing 753. 平方矩阵 I
AcWing 755. 平方矩阵 III
AcWing 755. 平方矩阵 III
88 0
AcWing 755. 平方矩阵 III
洛谷P2430-严酷的训练(一维01背包)
洛谷P2430-严酷的训练(一维01背包)
洛谷P2430-严酷的训练(一维01背包)