Cod sursa(job #942068)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 20 aprilie 2013 17:31:06
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#define eps 1e-12
using namespace std;
const char iname[] = "poligon.in";
const char oname[] = "poligon.out";
ifstream fin(iname);
ofstream fout(oname);
int N, M, i, j, ANS;
struct p{
	double x, y;
}Poly[808], Point;
inline int isLeft (p p0, p p1, p p2){
	double d = (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}
inline int wn_Point (p P, p Poligon[], int DM){
	int wn = 0;
	for (i = 1; i <= DM; ++i)
	{
		if (Poligon[i].y < P.y){
			if (Poligon[i + 1].y > P.y)
				if (isLeft(P, Poligon[i], Poligon[i + 1]) > 0)
					++wn;
		}
		else{
			if (Poligon[i + 1].y < P.y)
				if (isLeft(P, Poligon[i], Poligon[i + 1]) < 0)
					--wn;
		}
	}
	return wn;
}
int main()
{
	fin >> N >> M;
	for (i = 1; i <= N; ++i) fin >> Poly[i].x >> Poly[i].y;
	Poly[N + 1] = Poly[1];
	for (j = 1; j <= M; ++j)
	{
		fin >> Point.x >> Point.y;
		if (wn_Point(Point, Poly, N) != 0) ++ANS;
	}
	fout << ANS << '\n';
	return 0;
}