ACM常用算法(21)

ACM常考算法

typedef struct { double x,y; } Point;

int linecorss(Point p1,Point p2,Point p3,Point p4,Point *p) {

double k; //同一直线

if ((p4.x-p3.x)*(p1.y-p3.y)-(p4.y-p3.y)*(p1.x-p3.x)==0&&

(p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x)==0) return 2; //平行，不同一直线

if ((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)==0) return 0;

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

//k1=((p2.x-p1.x)*(p1.y-p3.y)-(p2.y-p1.y)*(p1.x-p3.x))/((p4.y-p3.y)*(p2.x-p1.x)-(p4.x-p3.x)*(p2.y-p1.y)); (*p).x=p1.x+k*(p2.x-p1.x); (*p).y=p1.y+k*(p2.y-p1.y); return 1;//有交点}

11.判断一个封闭图形是凹集还是凸集

语法：result=convex(Point *p,int n); 参数：

*p： 封闭曲线顶点数组 n： 封闭曲线顶点个数

返回

1：凸集；-1：凹集；0：曲线不符合要求无法计算 值： 注意： 源程序：

默认曲线为简单曲线：无交叉、无圈

typedef struct { double x,y; } Point;

int convex(Point *p,int n) {

int i,j,k; int flag = 0;