ACM常用算法(17)

ACM常考算法

源程序：

需要 math.h

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

int insidepolygon(Point *polygon,int N,Point p) {

int counter = 0; int i;

double xinters; Point p1,p2;

p1 = polygon[0];

for (i=1;i<=N;i++) { p2 = polygon[i % N];

if (p.y > MIN(p1.y,p2.y)) {

if (p.y <= MAX(p1.y,p2.y)) {

if (p.x <= MAX(p1.x,p2.x)) { if (p1.y != p2.y) { xinters =

(p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;

if (p1.x == p2.x || p.x <= xinters) counter++; } } } }

p1 = p2; }

if (counter % 2 == 0) return(OUTSIDE); else

return(INSIDE); }

6.判断点是否在线段上

语法：result=Pointonline(Point p1,Point p2,Point p); 参数：

p1、p2： 线段的两个端点 p： 被判断点

返回

0：点在不在线段上；1：点在线段上 值： 注意： 源程

若p线段端点上返回1 需要 math.h