Cod sursa(job #1396702)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 22 martie 2015 21:07:10
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <utility>

#define x first
#define y second
using namespace std;

struct line
{
	int a, b, c;
	line()
	{
		a = b = c = 0;
	}
	line(pair<int, int> A, pair<int, int> B)
	{
        a = B.y - A.y;
        b = A.x - B.x;
        c = (-a) * A.x - b * A.y;
	}
};

ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int kMax = 60010;
int n, m;
pair<int, int> poly[kMax];
line l[kMax];

int getRandomNumber()
{
	const int kMore = 60001;
	int r = rand() + kMore;
	return r;
}

bool areParallel(line a, line b)
{
	return (a.a * b.b - a.b * b.a == 0);
}

bool isOnSegment(double dx, double dy, pair<int, int> A, pair<int, int> B)
{
    double Ax = A.x, Ay = A.y, Bx = B.x, By = B.y;

	if (min(Ax, Bx) <= dx && dx <= max(Ax, Bx) && min(Ay, By) <= dy && dy <= max(Ay, By))
		return true;
	return false;
}

bool isInPolygon(pair<int, int> point)
{
	int intersections = 0;
    pair<int, int> rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
    for (int i = 1; i <= n; ++i)
	{
		line ray = line(point, rayOrigin);
		double det = ray.a * l[i].b - ray.b * l[i].a;

		while (areParallel(ray, l[i]))
		{
            rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
			ray = line(point, rayOrigin);
			det = ray.a * l[i].b - ray.b * l[i].a;
		}

		double solX = -(ray.c * l[i].b - l[i].c * ray.b) / det;
		double solY = -(ray.a * l[i].c - l[i].a * ray.c) / det;

		if (isOnSegment(solX, solY, poly[i], poly[i + 1]) && isOnSegment(solX, solY, point, rayOrigin))
			++intersections;
	}
    return (intersections % 2);
}

int main()
{
	srand(time(NULL));

	fin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		int x, y;	fin >> x >> y;
		poly[i] = make_pair(x, y);
	}
	poly[n + 1] = poly[1];
	for (int i = 1; i <= n; ++i)
        l[i] = line(poly[i], poly[i + 1]);

	int res = 0;
	while (m--)
	{
		int x, y;
		fin >> x >> y;
		if (isInPolygon(make_pair(x, y)))
			++res;
	}
	fout << res << '\n';
	return 0;
}