[LeetCode]Max Points on a Line

对于每一个point p我们可以calculate其他任意一个point和p的斜率，如果有多个point和p连成的直线斜率相同，说明他们在一条直线上。所以我们需要一个map来记录所有point和p连成直线的斜率。那么我们用什么来做map的key呢，如果我们用double来表示斜率那么我们要用double做key，但是由于double精度的关系，两个几乎一样的数可能被map视为两个不同的key，从而map有可能无法准确储存我们想要的信息。所以我们另建一个struct用来表示分数，我们自己定义==和hash function。当然为了避免2/3和4/6被视为不同slope的情况，我们需要每一次找到分子和分母的最大公约数(gcd)，然后分子分母除以gcd保证其不可约分。对于斜率为0和无穷的情况我们用0/+-1和+-1/0来表示。除此之外，我们还要统计和当前point p重合的所有点，因为无论结果为何，这些点都会在结果集里，因为这一轮里所有的line都经过p。时间复杂度O(n^2)，代码如下：