题意:中文的么,自己看喽。
析:很容易明白是判定点是不是在多边形内部,一般是向量来判定,我一开始用点在向量的右侧,因为是顺时针给的,只要点全在外侧或边上,
就可以,暴力一下就ok。由于这个是浮点数,一定要注意精度,也就是误差,结果WA了好几次,一气之下,我改了算法,采用转角法,
假想有一条向右的射线,统计多边形穿过这条射线正反多少次,顺时针减1,逆时针加1。一定要注意这个精度控制,不然就WA。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath> using namespace std;
const double eps = 1E-10;
const int maxn = 100 + 10;
struct node{
double x, y;
node() { }
node(double xx, double yy) : x(xx), y(yy) { }
};
node operator + (node A, node B) { return node(A.x+B.x, A.y+B.y); }
node operator - (node A, node B) { return node(A.x-B.x, A.y-B.y); }
int n;
node a[maxn]; int dcmp(double x){
if(fabs(x) < eps) return 0;
else return x < 0 ? -1 : 1;
} double cross(node A, node B){ return A.x * B.y - A.y * B.x; } bool solve(node p){
int wn = 0;
for(int i = 0; i < n; ++i){
int k = dcmp(cross(a[(i+1)%n]-a[i], p-a[i]));
int d1 = dcmp(a[i].y-p.y);
int d2 = dcmp(a[(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 true;
return false;
} int main(){
int m;
while(~scanf("%d", &n)){
for(int i = 0; i < n; ++i) scanf("%lf %lf", &a[i].x, &a[i].y);
scanf("%d", &m);
while(m--){
double x, y;
scanf("%lf %lf", &x, &y);
if(solve(node(x, y))) puts("Yes");
else puts("No");
}
}
return 0;
}