首页 > 代码库 > Cupid's Arrow---hdu1756(判断点与多边形的位置关系 模板)
Cupid's Arrow---hdu1756(判断点与多边形的位置关系 模板)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1756
题意:中文题,套模板即可;
/*射线法:判断一个点是在多边形内部,边上还是在外部,时间复杂度为O(n);射线法可以正确用于凹多边形;射线法是使用最广泛的算法,这是由于相比较其他算法而言,它不但可以正确使用在凹多边形上,而且不需要考虑精度误差问题。该算法思想是从点出发向右水平做一条射线,计算该射线与多边形的边的相交点个数,当点不在多边形边上时,如果是奇数,那么点就一定在多边形内部,否则,在外部。*/#include <stdio.h>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int N = 2010;const double eps = 1e-10;const int INF = 0x3f3f3f3f;//////////////////////////////////////////////////////////////////struct point{ double x, y; point(double x=0, double y=0) : x(x), y(y){} friend point operator - (const point& p1, const point& p2) { return point(p1.x-p2.x, p1.y-p2.y); } friend double operator ^ (const point& p1, const point& p2) { return p1.x*p2.y - p1.y*p2.x; }};//////////////////////////////////////////////////////////////////struct Segment{ point s, e;};/////////////////////////////////////////////////////////////////////判断一个double类型的数是 0 <0 >0;int Sign(double x){ if( fabs(x) < eps )return 0; if(x > 0)return 1; return -1;}/////////////////////////////////////////////////////////////////////判断o在ab的哪边;0:o在直线ab上; >0:在左边; <0:在右边;double cross(point o, point a, point b){ return ((a-o)^(b-o));}/////////////////////////////////////////////////////////////////////已知abc三点在一条直线上,判断点a是否在线段bc之间;<=0:在 >0:不在;int Between(point a, point b, point c){ if(fabs(b.x-c.x) > fabs(b.y-c.y)) return Sign(min(b.x, c.x)-a.x)*Sign(max(b.x, c.x)-a.x); else return Sign(min(b.y, c.y)-a.y)*Sign(max(b.y, c.y)-a.y);}/////////////////////////////////////////////////////////////////////判断点p0和线段S上,<=0:在,1:不在;int PointOnSegment(point p0, Segment S){ if(Sign(cross(S.s, S.e, p0)) == 0) return Between(p0, S.s, S.e); return 1;}/////////////////////////////////////////////////////////////////////求线段a和线段b的交点个数;int SegmentCross(Segment a, Segment b){ double x1 = cross(a.s, a.e, b.s); double x2 = cross(a.s, a.e, b.e); double x3 = cross(b.s, b.e, a.s); double x4 = cross(b.s, b.e, a.e); if(Sign(x1*x2)<0 && Sign(x3*x4)<0) return 1; if((Sign(x1)==0 && Between(b.s, a.s, a.e)<=0) || (Sign(x2)==0 && Between(b.e, a.s, a.e)<=0) || (Sign(x3)==0 && Between(a.s, b.s, b.e)<=0) || (Sign(x4)==0 && Between(a.e, b.s, b.e)<=0)) return 2; return 0;}/////////////////////////////////////////////////////////////////////判断点p0与含有n个节点的多边形的位置关系,p数组是顶点集合;///返回0:边上或顶点上, 1:外面, -1:里面;int PointInPolygon(point p0, point p[], int n){ Segment L, S; point temp; L.s = p0, L.e = point(INF, p0.y);///以p0为起点的射线L; int counts = 0; p[n] = p[0]; for(int i=1; i<=n; i++) { S.s = p[i-1], S.e = p[i]; if(PointOnSegment(p0, S) <= 0) return 0; if(S.s.y == S.e.y) continue;///和射线平行; if(S.s.y > S.e.y) temp = S.s; else temp = S.e; if(PointOnSegment(temp, L) == -1) counts ++; else if(SegmentCross(L, S) == 1) counts ++; } if(counts%2) return -1; return 1;}//////////////////////////////////////////////////////////////////int main(){ int n, m; point p[N]; while(scanf("%d", &n) != EOF) { for(int i=0; i<n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); scanf("%d", &m); for(int i=1; i<=m; i++) { double x, y; scanf("%lf %lf", &x, &y); int ans = PointInPolygon(point(x, y), p, n); if(ans <= 0)puts("Yes"); else puts("No"); } } return 0;}
Cupid's Arrow---hdu1756(判断点与多边形的位置关系 模板)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。