Cod sursa(job #1396840)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 23 martie 2015 07:42:00
Problema Poligon Scor 50
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.08 kb
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <utility>

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

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

ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int kMax = 60010;
int n, m;
pair<double, double> 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 - 1LL * a.b * b.a == 0.0);
}

bool isOnSegment(double dx, double dy, pair<double, double> A, pair<double, double> B)
{
	if (min(A.x, B.x) <= dx && dx <= max(A.x, B.x) && min(A.y, B.y) <= dy && dy <= max(A.y, B.y))
		return true;
	return false;
}

bool isInPolygon(pair<double, double> point)
{
	int intersections = 0;
    pair<double, double> 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)
	{
		double 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--)
	{
		double x, y;
		fin >> x >> y;
		if (isInPolygon(make_pair(x, y)))
			++res;
	}
	fout << res << '\n';
	return 0;
}