Cod sursa(job #776678)

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

using namespace std;

const double eps = 0.001;
typedef long long int64;

#define x first
#define y second

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

inline int intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int> p2)
{
	int64 a2 = (p1.y - p2.y), b2 = (p2.x - p1.x), c2 = (1LL * p1.x * p2.y - 1LL * p1.y * p2.x);
	if (a2 * P.x + b2 * P.y + c2 == 0 && P.y >= min(p1.y, p2.y) && P.y <= max(p1.y, p2.y) && P.x >= min(p1.x, p2.x) && P.x <= max(p1.x, p2.x)) onboard = 1;
	
	if (a2 == 0)
		return (P.y == p1.y && max(p1.x, p2.x) >= P.x ? 2 : 0);
	if (a2 < 0)
		a2 *= -1, b2 *= -1, c2 *= -1;
	
	if (P.y >= min(p1.y, p2.y) && P.y <= max(p1.y, p2.y))
		return 1LL * P.x * a2 <= (-P.y) * b2 - c2;
	else
		return 0;
}

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;
		onboard = 0;
		
		for (int j = 1; j <= N; ++j)
			nums += intersect(B, A[j], A[j + 1]);
		result += max(onboard, nums % 2);
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}