ACM常用算法(18)

ACM常考算法

序：

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

int FC(double x1,double x2) {

if (x1-x2<0.000002&&x1-x2>-0.000002)return 1;else return 0; }

int Pointonline(Point p1,Point p2,Point p) {

double x1,y1,x2,y2; x1=p.x-p1.x; x2=p2.x-p1.x; y1=p.y-p1.y; y2=p2.y-p1.y;

if (FC(x1*y2-x2*y1,0)==0)return 0;

if ((MIN(p1.x,p2.x)<=p.x&&p.x<=MAX(p1.x,p2.x))&& (MIN(p1.y,p2.y)<=p.y&&p.y<=MAX(p1.y,p2.y))) return 1;else return 0; }

7.判断两线段是否相交

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

p1～

两条线段的四个端点 4：

返回

0：两线段不相交；1：两线段相交；2两线段首尾相接 值： 注意： 源程序：

p1!=p2;p3!=p4;

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

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

Point tp1,tp2,tp3; if

((p1.x==p3.x&&p1.y==p3.y)||(p1.x==p4.x&&p1.y==p4.y)||(p2.x==p3.x&&p2.y==p3.y)||(p2.x==p4.x&&p2.y==p4.y)) return 2; //快速排斥试验 if

((MIN(p1.x,p2.x)<p3.x&&p3.x<MAX(p1.x,p2.x)&&MIN(p1.y,p2.y)<p3.y<MAX(p1.y,p2.y))||