首页 > 代码库 > ZOJ1081 Points Within
ZOJ1081 Points Within
PS: 判断点是否在多边形内,用的绕圈法,具体参见刘汝佳的训练指南。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> using namespace std; struct point { int x, y; point(double x=0, double y=0):x(x),y(y) {} }; point operator - (point A, point B) { return point(A.x-B.x, A.y-B.y); } double Cross(point A, point B) { return A.x*B.y - A.y*B.x; } vector<point> v; vector<point> Contain; vector<point> check; int n, m; const double eps = 1e-10; int dcmp(double x) { if(fabs(x)<eps) return 0; else return x < 0 ? -1 : 1; } double Dot(point a, point b) { return a.x*b.x + a.y*b.y; } bool OnSegment(point p, point a1, point a2) { return dcmp(Cross(a1-p, a2-p))==0 && dcmp(Dot(a1-p, a2-p))<=0; } int isPointIn(point p) { int wn = 0; for(int i = 0; i < n; i++) { if(OnSegment(p, v[i], v[(i+1)%n])) return 1; int k = dcmp(Cross(v[(i+1)%n]-v[i], p-v[i])); int d1 = dcmp(v[i].y-p.y); int d2 = dcmp(v[(i+1)%n].y-p.y); if(k>0 && d1<=0 && d2 > 0) wn++; if(k<0 && d2<=0 && d1 > 0) wn--; } if(wn!=0) return 1; else return 0; } int main() { int T = 1; point tmp; bool first = false; while(scanf("%d", &n)!=EOF && n) { if(first) printf("\n"); else first = true; scanf("%d", &m); v.clear(); Contain.clear(); for(int i = 0; i < n; i++) { scanf("%d%d", &tmp.x, &tmp.y); Contain.push_back(tmp); } for(int i = n-1; i >= 0; i--) { v.push_back(Contain[i]); } check.clear(); for(int i = 0; i < m; i++) { scanf("%d%d", &tmp.x, &tmp.y); check.push_back(tmp); } printf("Problem %d:\n", T++); for(int i = 0; i < m; i++) { int res = isPointIn(check[i]); if(res==1) printf("Within\n"); else printf("Outside\n"); } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。