作者tkcn (小安)
看板Prob_Solve
标题Re: [问题] 请问三点共线
时间Sun Apr 17 19:04:56 2011
※ 引述《chchwy (mat)》之铭言：
: Point a,b,c;
: int pos = a.x*b.y + b.x*c.y + c.x*a.y;
: int neg = a.x*c.y + b.x*a.y + c.x*b.y;
: if(pos==neg) {
: // They're on the same line
: }
: 请问在网路上我看到这种做法，可以判断三点共线。
: 但是我不太明白为什麽可以这样做?
: 我个人猜测应该是跟外积有关系
: 但是又式子又推不出来 冏
是外积没错，
先算出两向量 ab = <b.x-a.x, b.y-a.y>
ac = <c.x-a.x, c.y-a.y>
此向量的外积: (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y)
= (b.x*c.y - b.x*a.y - a.x*c.y + a.x*a.y)
- (c.x*b.y - c.x*b.y - b.y*a.x + a.x*a.y)
整理一下就跟上面的程式一样了，
不过我完全不认为写成那样有任何好处就是了，
直接判断 cross(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y)==0
比较容易理解。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.114.78.231