zoj 1081 Points Within 点与多边形关系

题目描述: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=81

题目大意: n 边形的 n 个顶点按顺序给出, 接下来是m 个测试点, 对于每个测试点判断该点是否在多边形内(包括边界).
直接copy 浙大模板 O(∩_∩)O哈哈~
附上代码

#include <cstdio>#include <cmath>#include <cstdlib>#define offset 10000#define eps 1e-8#define zero(x) ( ((x > 0) ? (x) : (-x)) < eps )struct point {    double x,y;};struct line {    point a,b;};double xmult(point p1,point p2,point p0) {    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}//判点在任意多边形内,顶点按顺时针或逆时针给出//on_edge表示点在多边形边上时的返回值,offset为多边形坐标上限int inside_polygon(point q,int n,point* p,int on_edge=1) {    point q2;    int i=0,count;    while (i<n)        for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset; i<n; i++)            if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)                return on_edge;            else if (zero(xmult(q,q2,p[i])))                break;            else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)                count++;    return count&1;}int main() {    point p[101];    point q;    int n, m;//多边形n 条边, m 个测试点    int k = 1;//第 k 个测试块儿,Problem k    while(scanf("%d", &n) && n) {        scanf("%d", &m);        for(int i = 0; i < n; i++)            scanf("%lf %lf", &p[i].x, &p[i].y);        if(k != 1)            printf("\n");        printf("Problem %d:\n", k++);        while(m--) {scanf("%lf %lf", &q.x, &q.y);            int ans = inside_polygon(q, n, p, 2);   //最后一个参数不小于1 即可            if(ans > 0)                printf("Within\n");            else                printf("Outside\n");        }    }    return 0;}