palantir 共线问题

palantir point test 4点共线问题 题目说了一句不能用计算和比较浮点数斜率!!!
想到 就是转化到比较整型的向量
转化到 x1 == x2  , check y1 ? y2

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

eetcode上的max num in a line 都是用double slope做的oj也全过了

ABCD四点共线转为判断两个三点共线，ABC和ABD。三点共线可以计算ABC这个三角形的面积，如果为0则共线，公式是AC和BC的叉乘，(A.x - C.x)*(B.y - C.y) - (A.y - C.y)*(B.x - C.x) == 0，只要这个等式成立就共线啦，注意两个向量都是以C为原点的。

ohmystill 发表于 2014-6-3 00:56
四点共线 是couresera 的 算法课的课后题啊 我给你找找

用浮点做的
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉
就一个 分母 和 一个 分子了
复写 equals();

假设这四个点分别是p1,p2,p3,p4。只需要判断p3,p4是否都在p1p2形成的直线就行了。判断p3是否在p1p2所有的直线，可以通过计算向量叉积来做，就是需要判断这个叉积的绝对值是否是两个向量长度的乘积，为了避免开方的浮点运算，可以两边同时平方，也就是计算 ((p2.x-p1.x)(p3.x-p1.x)+(p2.y-p1.y)(p3.y-p1.y))^2 =? ((p1.x-p2.x)^2+(p1.y-p2.y)^2)((p3.x-p1.x)^2+(p3.y-p1.y)^2),然后类似的方式判断p4，可能需要注意点是否重合的情况，不过这个方程可能已经包含了这种情况。
其实，不用计算斜率，也可以利用斜率的比较来判断，例如判断p1,p2,p3是否共线，是可以计算两个斜率，然后看绝对值是否相同，同时也可以对斜率比较做简单的变现，直接使用下面的方程：
(p2.x-p1.x)(p3.y-p1.y) =? (p3.x-p1.x)*(p2.y-p1.y), （考虑绝对值的情况，可以两边同时平方）这个本质是比较斜率，只不过不用在计算斜率了。

题目 提示不能用浮点数的运算和比较，所以只能用整型的加减乘和求余吧

不要沉。。。有没有人做过这个，请教一下好方法

四点共线 是couresera 的 算法课的课后题啊 我给你找找

ohmystill 发表于 2014-6-2 11:59
用浮点做的
转化成 整形向量可以啊
用一个类来存值 里面自动实例化的时候 就把公约数约掉

你意思是还是算slope, 不过存成分数的形式，然后比较整型向量？但是加上求最大公约数这个performance就很慢了吧

应该是"点积",不是叉积。

wendychueng 发表于 2014-6-3 03:58
你意思是还是算slope, 不过存成分数的形式，然后比较整型向量？但是加上求最大公约数这个performance就很 ...

cracking the coding interview 原题.
page 272

哦 不能比较...
- = 能不能算个方程? 然后带数进去...