Cod sursa(job #342225)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 20 august 2009 21:58:26
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>

using namespace std;

const int MAXN = 810;
const int INF = 100000;
const double eps = 0.00000001;

#define MP make_pair
#define ff first
#define ss second

int N, M, L, Sol;
int A[MAXN], B[MAXN], X[MAXN];
vector <int> V[MAXN];
double medx;
set <pair <int, pair <int, int> > > S;

inline double getY(int i, double x)
{
	assert(A[i] != A[i+1]);

	double m = (double) (B[i+1] - B[i]) / (A[i+1] - A[i]);
	double n = B[i] - m * A[i];

	return m*x + n;
}

inline int cmp(int i, int j)
{
	return getY(i, medx) < getY(j, medx);
}

int isInside(int i, int x, int y)
{
	int front = 0, middle, back = V[i].size() - 1, res = -1;

	while (front <= back)
	{
		middle = (front + back) / 2;

		if (getY(V[i][middle], x) <= y) 
		{
			res = middle;
			front = middle + 1;
		}
		else back = middle - 1;
	}
	
	if (res >= 0 && fabs(getY(V[i][res], x) - y) < eps) return 1;
	if (res+1 < (int) V[i].size() && fabs(getY(V[i][res+1], x) - y) < eps) return 1;

	return !(res&1);
}

int main()
{
	ifstream fin("poligon.in");
	ofstream fout("poligon.out");

	fin >> N >> M;

	for (int i = 1; i <= N; ++i) 
	{
		fin >> A[i] >> B[i];
		X[i] = A[i];
	}

	A[N+1] = A[1], B[N+1] = B[1];

	X[0] = -1;
	sort(X, X+N+1);
	L = unique(X, X+N+1) - X;
	X[L] = INF;

	for (int i = 1; i <= N; ++i)
		for (int j = 0; j < L; ++j)
		{
			if ((A[i] <= X[j] && X[j+1] <= A[i+1]) || (A[i+1] <= X[j] && X[j+1] <= A[i])) V[j].push_back(i);
			if (A[i] == A[i+1] && A[i] == X[j]) S.insert(MP(X[j], MP( min(B[i], B[i+1]), max(B[i], B[i+1]))));
		}

	for (int i = 0; i < L; ++i) 
	{
		medx = (X[i] + X[i+1]) / 2.0;

		sort(V[i].begin(), V[i].end(), cmp);
	}

	for (int i = 1; i <= M; ++i)
	{
		int x, y;
		fin >> x >> y;
		int j = upper_bound(X, X+L, x) - 1 - X;

		if (X[j] != x) Sol += isInside(j, x, y);
		else {
				 set < pair <int, pair <int, int> > > :: iterator it = --S.upper_bound(MP(x, MP(y, INF)));
				 Sol += it->ss.ff <= y && y <= it->ss.ss;
		     }
	}

	fout << Sol << endl;

	return 0;
}