Polygon-Point-Containment
For a given polygon g and target points t, print "2" if g contains t, "1" if t is on a segment of g, "0" otherwise.
g is represented by a sequence of points p1, p2,..., pn where line segments connecting pi and pi+1 (1 ≤ i ≤ n−1) are sides of the polygon. The line segment connecting pn and p1 is also a side of the polygon.
Note that the polygon is not necessarily convex.
Input
The entire input looks like:
g (the sequence of the points of the polygon) q (the number of queris = the number of target points) 1st query 2nd query : qth query
g is given by coordinates of the points p1,..., pn in the following format:
n x1 y1 x2 y2 : xn yn
The first integer n is the number of points. The coordinate of a point pi is given by two integers xi and yi. The coordinates of points are given in the order of counter-clockwise visit of them.
Each query consists of the coordinate of a target point t. The coordinate is given by two intgers x and y.
Output
For each query, print "2", "1" or "0".
Constraints
- 3 ≤ n ≤ 100
- 1 ≤ q ≤ 1000
- -10000 ≤ xi, yi ≤ 10000
- No point of the polygon will occur more than once.
- Two sides of the polygon can intersect only at a common endpoint.
Sample Input
4 0 0 3 1 2 3 0 3 3 2 1 0 2 3 2
Sample Output
2 1 0
题意：
存在一多边形g（凹凸不确定），给定g每个点的横纵坐标，再询问n个点与多边形的位置关系，如果点在多边形内部输出2，如果点在多边形的边上则输出1，如果在多边形外则输出0；
题解：
针对本题我们可以利用射线法来判断点与多边形的位置关系：
简而言之，就是从该点向任意方向发射一条射线，看这条射线与多边形的边相交多少次，如果为奇数次，那么该点在多边形内部，如果是偶数次，在该点在多边形的外部。
然而这里有很多需要注意的细节和边界问题，譬如假设该射线与多边形的一条边重合，亦或者是射线刚好交到多边形的一个顶点怎么办？？
针对这种问题主要有两种解决方案：
一种是OI选手常用的但是精度可能略低的方法，随机一个角度。因为角度是无限多的，而多边形的边是有限条，所以总存在一个角度的射线既不与边重合，也不和点相交。
另一种就是背一个分类讨论好的，不会错的板子 （我就是后者）
so板子如下：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 110;
const double eps = 1e-10;
const double PI = acos(-1);
int n, m;
int dcmp(double x) // 计算几何里面判断 符号，或者0的函数 （确保精度）
{
if (fabs(x) <= eps) return 0;
if(x > 0) return 1;
return -1;
}
struct Point
{
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) { } // 结构体内构造函数
Point operator- (const Point& t) // 重载，方便向量运算
{
return Point(x - t.x, y - t.y);
}
double operator^ (const Point& t) //重载一下叉乘运算
{
return x * t.y - t.x * y;
}
}p[N];
typedef Point Vector; // 向量
Point P;
double dot(Vector A, Vector B) // 点乘
{
return A.x * B.x + A.y * B.y;
}
bool On_segment(Point A, Point B, Point P) // 判断点在线段上的函数
{
// 叉乘 == 0 表示 向量 P-A 和 P-B 共线 点乘小于等于 0 表示 点落在线段上，而不是一侧
return dcmp((P - A) ^ (P - B)) == 0 && dcmp(dot(A - P, B - P)) <= 0;
}
int In_Polygon(Point P)
{
bool flag = 0;
Point P1, P2;
for (int i = 1, j = n; i <= n; j = i++) // （两邻点确定一条边）遍历多边形的所有边
{
P1 = p[i];
P2 = p[j];
if (On_segment(P1, P2, P)) return 1; // 如果点在边上 返回 1
//前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
//后一个判断被测点 在 射线与边交点 的左边
if ((dcmp(P1.y - P.y) > 0 != dcmp(P2.y - P.y) > 0) && dcmp(P.x - (P.y - P1.y) * (P1.x - P2.x) / (P1.y - P2.y) - P1.x) < 0)
{
flag = !flag;
}
}
if (flag) return 2;
else return 0;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
cin >> m;
for(int i = 1; i <= m; i++)
{
cin >> P.x >> P.y;
cout << In_Polygon(P) <<endl;
}
return 0;
}