ZOJ1081 Points Within

痛定思痛。 2021-09-30 16:26 267阅读 0赞

[嘟嘟嘟][Link 1]

题面：给一个\\(n\\)个点的多边形和\\(m\\)个点，判断每一个点是否在多边形内。

解法：射线法。  
就是从这个点引一条射线，如果与多边形有奇数个交点，则在多边形内部。  
那么只用枚举每一条边，然后判断这条边与射线有无交点。为了方便，射线为水平的。然后可以用叉积判断三点共线，以及多边形的两个端点纵坐标的大小关系。  
但要注意一些特殊情况，比如有一个交点是多边形的顶点，所以为了避免重复统计，需要规定交在每一条边的下断点还是上端点。

#include<cstdio> #include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdlib> #include<cctype> #include<vector> #include<stack> #include<queue> using namespace std; #define enter puts("") #define space putchar(' ') #define Mem(a, x) memset(a, x, sizeof(a)) #define rg register typedef long long ll; typedef double db; const int INF = 0x3f3f3f3f; const db eps = 1e-8; const int maxn = 105; inline ll read() { ll ans = 0; char ch = getchar(), last = ' '; while(!isdigit(ch)) last = ch, ch = getchar(); while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar(); if(last == '-') ans = -ans; return ans; } inline void write(ll x) { if(x < 0) x = -x, putchar('-'); if(x >= 10) write(x / 10); putchar(x % 10 + '0'); } int n, m; struct Vec { int x, y; db operator * (const Vec& oth)const { return x * oth.y - oth.x * y; } friend int dot(const Vec& A, const Vec& B) { return A.x * B.x + A.y * B.y; } }; struct Point { int x, y; Vec operator - (const Point& oth)const { return (Vec){x - oth.x, y - oth.y}; } }A[maxn], P; bool judge() { int cnt = 0; A[n + 1] = A[1]; for(int i = 1; i <= n; ++i) { int d = (P - A[i]) * (P - A[i + 1]); if(!d && dot(A[i] - P, A[i + 1] - P) <= 0) return 1; //点在边上 int d1 = A[i].y - P.y, d2 = A[i + 1].y - P.y; if(d > 0 && d1 >= 0 && d2 < 0) cnt ^= 1; if(d < 0 && d1 < 0 && d2 >= 0) cnt ^= 1; } return cnt; } int main() { int cnt = 0; while(scanf("%d", &n) && n) { if(++cnt != 1) enter; printf("Problem %d:\n", cnt); m = read(); for(int i = 1; i <= n; ++i) A[i].x = read(), A[i].y = read(); for(int i = 1; i <= m; ++i) { P.x = read(); P.y = read(); puts(judge() ? "Within" : "Outside"); } } return 0; }

转载于:https://www.cnblogs.com/mrclr/p/9974320.html

[Link 1]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1081