判断点是否在多边形内 扫描法

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

struct point {
	double x, y;
};

struct v {
	point start, end;
};


double dotProduct(v v1, v  v2) {
	return (v1.end.x - v1.start.x)*(v2.end.x - v2.start.x) + (v1.end.y - v1.start.y)*(v2.end.y - v2.start.y);
}
double crossProduct(v v1, v v2) {
	return (v1.end.x - v1.start.x)*(v2.end.y - v2.start.y) - (v2.end.x - v2.start.y)*(v1.end.y - v1.start.y);
}

bool onSegment(point p1, point p2, point p0) {
	if (fabs((p1.x - p2.x)*(p1.y - p0.y) - (p1.x - p0.x)*(p1.y - p2.y))<1e-7 &&
		min(p1.x, p2.y) <= p0.x&&max(p1.x, p1.x) >= p0.x&&
		min(p1.y, p2.y) <= p0.y&&max(p1.y, p2.y) >= p0.y
		)
		return true;
	return false;
}

point polygon[100];
//n表示多边形的顶点个数
bool inPolygon(point *polygon,point p,int n) {
	int cnt = 0;
	point p1, p2;
	for (int i = 0; i < n; i++) {
		p1 = polygon[i];
		p2 = polygon[(i + 1) % n];

		//判断点是否在多边形上
		if (onSegment(p1, p2, p)) return  true;

		//这是排除(b)种情况
		if(p.y>min(p1.y,p2.y))
			if (p.y <= max(p1.y, p2.y)) 
				//排除p1p2和射线平行的情况
				if (p1.y != p2.y) {
					//这是求出线段和过该点的射线的交点
					int x0 = (p.y - p1.y) / (p2.y - p1.y)*(p2.x - p1.x) + p1.x;
					if (p.x <= x0)  cnt++;
				}
	}
	if (cnt % 2 == 0) return false;
	else return true;
}



int main() {
	int n;
	point p;
	while (cin >> n) {
		for (int i = 0; i < n; i++)
			cin >> polygon[i].x >> polygon[i].y;
		cin >> p.x >> p.y;
		cout << inPolygon(polygon, p, n) << endl;
	}
}