ACM常用算法(19)

ACM常考算法

(MIN(p1.x,p2.x)<p4.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y))) ;else return 0;

//跨立试验

tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;

if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return 1;else return 0; }

8.判断线段与直线是否相交

语法：result=lineintersect(Point p1,Point p2,Point p3,Point p4); 参数：

p1、p2： 线段的两个端点 p3、p4： 直线上的两个点

返回

0：线段直线不相交；1：线段和直线相交 值： 注意： 源程序：

如线段在直线上，返回 1

typedef struct { double x,y; } Point;

int lineintersect(Point p1,Point p2,Point p3,Point p4) {

Point tp1,tp2,tp3; tp1.x=p1.x-p3.x; tp1.y=p1.y-p3.y; tp2.x=p4.x-p3.x; tp2.y=p4.y-p3.y; tp3.x=p2.x-p3.x; tp3.y=p2.y-p3.y;

if ((tp1.x*tp2.y-tp1.y*tp2.x)*(tp2.x*tp3.y-tp2.y*tp3.x)>=0)return 1;else return 0; }

9.点到线段最短距离

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

p1、

线段的两个端点 p2：