hust 1607 Triangles(经典好题)

题意:给出一定的点,然后再给出哪些点相连,问最后这些相连点的组成多少个三角形,hash的应用

分析:转载牛人的思想

题意:给一些点的坐标和里面的点构成的一些线段,求这些线段可以构成多少个三角形;

思路:因为的点的个数只有100,所以枚举三个点就可以了,O(n^3);

只不过这里有一些条件:这三个点构成的三条线段必须在前面给的线段里,怎么判断呢?

这里我们可以用hash坐标的方法,把一个点的坐标hash成一个数字,这个很简单,就是把

每个点的x,y坐标加上100000,最后key=x*200000+y,因为y不会超过200000,所以

这样就可以保证每个点的坐标不相同了,然后我们再把key和坐标的序号建立一个映射就好了;

再然后我们可以为100点建立一个邻接矩阵,开始输入数据的时候,每来一个线段,我们找到

线段两端的坐标得到它的hash值,并用映射关系找到这个点的序号,然后把邻接矩阵里两个序

号对应的位置赋值为1,例如现在线段两个端点的序号是1和2,map[][]为链接矩阵,那么我们

就令map[1][2]=map[2][1]=1,像加了一条边一样,这样我们就得到了所有点与点之间的关系了;

接下来我们还要解决一个问题,比如线段ab和bc平行,那么我们就又可以得到一条新的线段也就是ac,

解决这个问题我们可以用点疏松的方法,这个类似于floyd算法,时间复杂度O(n^3),具体看

下面是大神的代码 

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<map>
using namespace std;
struct node {double x,y;};
node point[220];
double yy[220];

map <double,int > pp ;
double get(double x,double y) //点hash
{
//    x+=100000;
//    y+=100000;
    x*=200000;
    x+=y;
    return x;
}
int mp[220][220];

double dis(node a,node b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int judgeline(node a,node b,node c)//判断线段共线 注意垂直的时候斜率为0  要单独判断啊
{
    double x,y,z,t;
    x=a.x-c.x;
    y=a.y-c.y;
    z=b.x-c.x;
    t=b.y-c.y;
    if((t<1e-8&&t>-1e-8)&&(y<1e-8&&y>-1e-8))return 1;
    else
    {
        if((t<1e-8&&t>-1e-8)||(y<1e-8&&y>-1e-8))return 0;
        t=(x/y)-(z/t);
        return (t<1e-8&&t>-1e-8);
    }
}
int subjudge(node a,node b,node c)//判断三角形
{
    double x,y,z;
    x=dis(a,b);
    y=dis(a,c);
    z=dis(b,c);
    if(x+y-z>1e-8&&x+z-y>1e-8&&y+z-x>1e-8)
        return 1;
    else return 0;
}
int judge(int a,int b,int c) //判断3个点的关系是否满足
{
    if(mp[a][b]&&mp[a][c]&&mp[b][c])
        return subjudge(point[a],point[b],point[c]);
    else return 0;
}
int main()
{
    int n,m,a,b,i,j,k,sum;
    double x1,y1,x2,y2;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        pp.clear();//这里清零很重要不要再忘记了
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&point[i].x,&point[i].y);
            yy[i]=get(point[i].x,point[i].y); //点hash
            pp[yy[i]]=i; //点与序号的映射
        }
        memset(mp,0,sizeof(mp));
        for(i=0;i<m;i++) //建立邻接矩阵
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a=pp[get(x1,y1)];
            b=pp[get(x2,y2)];
            mp[a][b]=1;
            mp[b][a]=1;
        }
        for(i=0;i<n;i++) //点疏松
        {
            for(j=0;j<n;j++)
            {
                if(i!=j)
                {
                    for(k=0;k<n;k++)
                    {
                        if(i!=k&&i!=j&&j!=k)
                        {
                            if(!mp[j][k]&&mp[i][j]&&mp[i][k]&&judgeline(point[i],point[j],point[k]))
                                mp[j][k]=1,mp[k][j]=1;
                        }
                    }
                }
            }
        }
        sum=0;
        for(i=0;i<n;i++) //三角形枚举并判断
            for(j=i+1;j<n;j++)
                for(k=j+1;k<n;k++)
                    sum+=judge(i,j,k);
                printf("%d\n",sum);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

1283 最小周长

1283 最小周长 题目来源: Codility 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 一个矩形的面积为S,已知该矩...

2986
来自专栏ACM算法日常

将树围起来(几何凸包)- HDU 1392

在二维欧几里得空间中,凸包可想象为一条刚好包著所有点的橡皮圈。如下图所示。计算凸包也就是求得外围(蓝线上)的那些点。

982
来自专栏崔庆才的专栏

TensorFlow layers模块用法

TensorFlow 中的 layers 模块提供用于深度学习的更高层次封装的 API,利用它我们可以轻松地构建模型,这一节我们就来看下这个模块的 API 的具...

1.1K8
来自专栏小鹏的专栏

tf API 研读2:math

TF API数学计算 tf...... :math (1)刚开始先给一个运行实例。         tf是基于图(Graph)的计算系统。而图的节点则是由操作(...

7815
来自专栏小小挖掘机

大过年的,一起来用Seq2Seq来作对联吧!

Seq2Seq全称Sequence to Sequence,在机器翻译、文章摘要等领域有着广泛的应用。其本身很简单,是一个如下图所示的Encoder-Decod...

1.3K8
来自专栏程序员互动联盟

【编程基础】C语言产生随机数需要了解的几个函数

C语言产生随机数是一个常见的编程功能任务,当然这个也不难,调用两三个函数就出来了,但是你知道这些函数具体是起到怎样的作用,并且是它们是如何产生随机数的吗? 几...

3477
来自专栏深度学习之tensorflow实战篇

python 中numpy基本方法总结可以类推tensorflow

一、数组方法 创建数组:arange()创建一维数组;array()创建一维或多维数组,其参数是类似于数组的对象,如列表等 反过来转换则可以使用numpy.n...

6105
来自专栏CDA数据分析师

Python之numpy数组学习(二)

前言 前面我们学习了numpy库的简单应用,今天来学习下比较重要的如何处理数组。 处理数组形状 下面可将多维数组转换成一维数组时的情形。 利用以下函数处理数组的...

2768
来自专栏mathor

科学计算库Numpy

 genfromtxt函数里穿了三个参数,分别是 要打开的文档名称,分隔符,以什么类型存储  打印结果:

1194
来自专栏chenjx85的技术专栏

leetcode-896-单调数列

如果对于所有 i <= j,A[i] <= A[j],那么数组 A 是单调递增的。 如果对于所有 i <= j,A[i]> = A[j],那么数组 A 是单调递...

1363

扫码关注云+社区

领取腾讯云代金券