题目链接:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=81
题目的很简单:给你一个多边形,再给你一系列的点,问你这些是否在多边形内。输出这些点与多边形的关系。。
学到了一种射线法判断点是否在多变型内。通过点在水平或者竖直引一条射线,看与多边形的交点个数。奇数就是在多边形内,偶数就是在多边形外。最开始,我是很怀疑这种方法的。主要还是射线穿过端点的情况。
对于上面的情况:
我们对于穿过端点的射线,交点算几次呢??我们这里只算一次。为了统一,我们要求这样来进行统计交点。
1.平行和重合于射线的多边形边不算。
2.对于相交于端点的交点,如果该点是该边的较高点(y值较大),算一次。。
基本上这样就可以了。。
Code:
#include <iostream> #include <algorithm> #include <cstdio> #include <cstring> #include <cmath> using namespace std; const int N = 105; const double eps = 1e-8; const double pi = acos(-1); const double INF = 0x3f3f3f3f; //点 struct POINT { double x, y; POINT(){ } POINT(double a, double b){ x = a; y = b; } }p[N]; //线段 struct Seg { POINT a, b; Seg() { } Seg(POINT x, POINT y){ a = x; b = y; } }; //直线 struct Line { POINT a, b; Line() {} Line(POINT x, POINT y){ a = x; b = y; } }; //叉乘 double cross(POINT o, POINT a, POINT b) { return (a.x - o.x) * (b.y - o.y) - (b.x - o.x) * (a.y - o.y); } //求两点间的距离 double dis(POINT a, POINT b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } int n, m, k; //两条直线的位置关系,平行,重合和相交 int Line_cross(Seg l1, Seg l2) { //两条直线平行 if(fabs(cross(l1.a, l2.a, l2.b) - cross(l1.b, l2.a, l2.b)) < eps && fabs(cross(l1.a, l2.a, l2.b)) > eps) return 0; //重合.. if(fabs(cross(l1.a, l2.a, l2.b)) < eps && fabs(cross(l1.b, l2.a, l2.b)) < eps) return 2; //有交点/// return 1; } //判断点在线段上 bool On_Seg(POINT a, Seg s) { if(fabs(cross(a, s.a, s.b)) > eps) return false; double maxx = max(s.a.x, s.b.x), minx = min(s.a.x, s.b.x); double maxy = max(s.a.y, s.b.y), miny = min(s.a.y, s.b.y); if(a.x >= minx && a.x <= maxx && a.y >= miny && a.y <= maxy) return true; return false; } //判断线段相交 bool Seg_cross(Seg s1, Seg s2) { double cs1 = cross(s1.a, s2.a, s2.b); double cs2 = cross(s1.b, s2.a, s2.b); double cs3 = cross(s2.a, s1.a, s1.b); double cs4 = cross(s2.b, s1.a, s1.b); // 互相跨立 if(cs1 * cs2 < 0 && cs3 * cs4 < 0) return true; if(On_Seg(s1.a, s2)) return true; if(On_Seg(s1.b, s2)) return true; if(On_Seg(s2.a, s1)) return true; if(On_Seg(s2.b, s1)) return true; return false; } bool PointInPolygon(POINT q) { int cnt = 0; Seg s(q, POINT(INF, q.y)); p[n] = p[0]; for(int i = 0; i < n; i ++){ if(On_Seg(q, Seg(p[i], p[i + 1]))) { return true; } //平行重合者不算... if(Line_cross(s, Seg(p[i], p[i + 1])) == 0 || Line_cross(s, Seg(p[i], p[i + 1])) == 2) continue; if(!Seg_cross(s, Seg(p[i], p[i + 1]))) continue; int on = -1; if(On_Seg(p[i], s)) on = i; if(On_Seg(p[i + 1], s)) on = i + 1; if(on != -1){ if(fabs(p[on].y - max(p[i].y, p[i + 1].y)) < eps) cnt ++; } else cnt ++; } return cnt % 2; } int main() { // freopen("11.txt", "r", stdin); k = 1; 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) puts(""); printf("Problem %d:\n", k ++); for(int i = 0; i < m; i ++){ POINT test; scanf("%lf %lf", &test.x, &test.y); if(PointInPolygon(test)) puts("Within"); else puts("Outside"); } } return 0; }
----->
又学习了。。