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



目录
相关文章
|
6月前
|
算法
【Leetcode 74】搜索二维矩阵 —— 二分查找|矩阵
给你一个满足下述两条属性的`m x n`整数矩阵:每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数
|
6月前
leetcode-542:01 矩阵
leetcode-542:01 矩阵
41 0
|
算法 C++
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
【每日算法Day 64】LeetCode 861. 翻转矩阵后的得分
|
算法 Java
算法打卡Day25_leetcode _461. 汉明距离
算法打卡Day25_leetcode _461. 汉明距离
算法打卡Day25_leetcode _461. 汉明距离
|
索引
leetcode题解 - 转置矩阵
给你一个二位整数数组matrix,返回matrix的转置矩阵。 矩阵的转置是指将矩阵的主对角线反转,交换矩阵的行索引与列索引
176 0
leetcode题解 - 转置矩阵
|
C语言 UED
[解题报告]【第33题】给定一个 n X n 的矩阵,求它的转置矩阵
[解题报告]【第33题】给定一个 n X n 的矩阵,求它的转置矩阵
|
算法 C语言 UED
[解题报告]【第35题】给定两个 a X b 和 c X d 的矩阵 ,求两个矩阵的乘积
[解题报告]【第35题】给定两个 a X b 和 c X d 的矩阵 ,求两个矩阵的乘积
|
机器学习/深度学习 人工智能 BI