Cod sursa(job #776658)

Utilizator darrenRares Buhai darren Data 10 august 2012 10:21:42
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <utility>

using namespace std;

const double eps = 0.00001;

#define x first
#define y second

int N, M;
pair<int, int> A[802];
pair<int, int> B;
int result;

inline bool intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int> p2)
{
	int b1 = 1, c1 = -P.y;
	int a2 = (p1.y - p2.y), b2 = (p2.x - p1.x), c2 = (p1.x * p2.y - p1.y * p2.x);
	
	if (a2 == 0)
		return (P.y == p1.y && max(p1.x, p2.x) >= P.x);
	
	double px = 1.0 * (c1 * b2 - c2 * b1) / (a2 * b1);
	double py = -1.0 * c1 / b1;
	
	if (py - min(p1.y, p2.y) > -eps && py - max(p1.y, p2.y) < eps)
		return px - P.x > -eps;
	else
		return false;
}

int main()
{
	ifstream fin("poligon.in");
	ofstream fout("poligon.out");
	
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
		fin >> A[i].x >> A[i].y;
	A[N + 1] = A[1];
	
	for (int i = 1; i <= M; ++i)
	{
		fin >> B.x >> B.y;
		
		int nums = 0;
		for (int j = 1; j <= N; ++j)
			if (intersect(B, A[j], A[j + 1]))
				++nums;
		result += nums % 2;
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}