Codeforces Gym 101466C – Planet Communcation

本题要计算从地球最少发射多少次信号可以与所有星球通讯。题设的条件中表示射线可以到达发射方向以及发射方向的反方向,实际上就是一条直线。那么我们只要知道地球点可以和剩下的n-1个坐标点组成多少个不同的方向向量cnt,就可以知道最少发射多少次,即刚刚统计算的cnt。

那么问题来了,怎么判断方向向量是否相同?这里我们要又一个概念就是**最简式相同**。最简式满足如下定义:

1. $(0,0,0)$的最简式是$(0,0,0)$;

2. $(x,0,0),(0,y,0),(0,0,z)$的最简式为$(1,0,0),(0,1,0),(0,0,1)$, 即**与坐标轴平行的向量取单位方向向量**;

3. $(x,y,0),(x,0,z),(0,y,z)$,这种类型的坐标满足$x、y、z$中有一个为0,其它均不为0,那么把两个不为0的进行约分,即$$ \left( \frac {x}{gcd(x,y)},\frac {y}{gcd(x,y)},0 \right) $$,同理可推到后两种。

4. $(x,y,z)$三个元素都不为0时,方向向量为$$ \left( \frac {x}{gcd(x,y,z)},\frac {y}{gcd(x,y,z)},\frac {z}{gcd(x,y,z)} \right) $$.

不难看出,这么讨论的原因有二。一是统一规定与坐标轴平行的方向向量,而是避免gcd(a,b)的报错。

在统计环节中,我用到了STL中的set容器,该容器负责处理一个集合,size()方法返回集合中的元素个数,非常好用。由于该容器采用了红黑树的平衡二叉树数据结构,所以如果往里扔结构体,需要重载<(小于号)运算符,重载时要保证大小比较明确。

 

说点什么

avatar
50
  Subscribe  
提醒