ACM常用算法(20)

ACM常考算法

q： 判断点

返回

点q到线段p1p2的距离 值： 注意： 源程序：

需要 math.h

#define MIN(x,y) (x < y ? x : y)#define MAX(x,y) (x > y ? x : y) typedef struct { double x,y; } Point;

double mindistance(Point p1,Point p2,Point q) {

int flag=1; double k; Point s;

if (p1.x==p2.x) {s.x=p1.x;s.y=q.y;flag=0;} if (p1.y==p2.y) {s.x=q.x;s.y=p1.y;flag=0;} if (flag) {

k=(p2.y-p1.y)/(p2.x-p1.x);

s.x=(k*k*p1.x+k*(q.y-p1.y)+q.x)/(k*k+1); s.y=k*(s.x-p1.x)+p1.y; }

if (MIN(p1.x,p2.x)<=s.x&&s.x<=MAX(p1.x,p2.x))

return sqrt((q.x-s.x)*(q.x-s.x)+(q.y-s.y)*(q.y-s.y)); else

return

MIN(sqrt((q.x-p1.x)*(q.x-p1.x)+(q.y-p1.y)*(q.y-p1.y)),sqrt((q.x-p2.x)*(q.x-p2.x)+(q.y-p2.y)*(q.y-p2.y))); }

10.求两直线的交点

语法：result=mindistance(Point p1,Point p2,Point q); 参数：

p1～

直线上不相同的两点 p4：

*p： 通过指针返回结果

返回

1：两直线相交；2：两直线平行 值： 注意： 源程序：

如需要判断两线段交点，检验k和对应k1（注释中）的值是否在0～1之间，用在0～1之间的那个求交点