3 2019/2/7
点和直线
判断点P在直线AB的左侧还是右侧
P
A B
B P
计算 AP×AB 结果为正，则在右侧 结果为负，则在左侧
A 注意：A.y<B.y
AP×AB = 0, P在AB上
4 2019/2/7
思考
怎么判断点P是否在线段AB上？ (1) PA×PB = 0 (2) A.x <= P.x <=B.x， A.y<=P.y<=B.y
注意事项（续）
尽量少用除法，开方，三角函数，容易 失去精度。用除法时注意除数不为0。 输出的时候要小心-0.00000，比如 a=-0.0000001，printf(“%.5lf”,a);
47 2019/2/7
注意事项（续）
考虑特殊情况
– 直线斜率是否为0，或斜率不存在 – 线段交点在端点上 – 点刚好在多边形上等等
31 2019/2/7
points[n] 记录已排序的n个点的坐标 result[ ] 记录凸包点集 （result是个栈,top是其指针） 初始化： result = {P0, P1, P2}, top = 3
32 2019/2/7
for (int i=3; i<n; i++) { 1. while (result[top-2]在直线result[top-1] points[i] 的顺时针方向) { top--;} 2. result.push(points[i]); }
13 2019/2/7
p点关于f点旋转α角度后的点q
q 以f为原点，建立新坐标系。 新坐标系中p的坐标为p’ 将p化成极坐标(r, θ) q’ = (r, θ+a) 将q’转化成直角坐标系 求q’在原坐标系的位置q
