Cod sursa(job #597319)

Utilizator savimSerban Andrei Stan savim Data 21 iunie 2011 19:54:42
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.42 kb
#include <stdio.h>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

#define MAX_N 810
#define MAX_C 60010

#define mp make_pair

int n, m, T, nrV, nrE, sol;

int P[MAX_N], stop[MAX_N];

int sector[MAX_C];

vector <int> E[MAX_N];

set <pair <int, int> > V[MAX_N];

struct punct {
	int x, y;
} A[MAX_N], Q;

double midX;

inline int next(int x) {
	if (x < n)
		return x + 1;
	return 1;
}

inline double coordY(int i) {
	double m = 1.0 * (A[i].y - A[next(i)].y) / (A[i].x - A[next(i)].x);
	double n = A[i].y - m * A[i].x;

	return m * midX + n;
}

inline int cmp(int p, int q) {
	return coordY(p) < coordY(q);
}

void solve() {
	sort(P + 1, P + n + 1);
	int m = unique(P + 1, P + n + 1) - P - 1;

	for (int i = 1; i <= n; i++) {
		if (A[i].x != A[next(i)].x) {
			for (int j = 1; j < m; j++)
				if (min(A[i].x, A[next(i)].x) <= P[j] && P[j + 1] <= max(A[i].x, A[next(i)].x))
					E[j].push_back(i);
		}
		else
			V[A[i].x].insert(mp(min(A[i].y, A[next(i)].y), max(A[i].y, A[next(i)].y)));

    	V[A[i].x].insert(mp(A[i].y, A[i].y));
	}

	for (int i = 1; i < m; i++) {
		sector[P[i]] = i;
    	
		midX = (P[i] + P[i + 1]) / 2.0;
		sort(E[i].begin(), E[i].end(), cmp);
	}

	for (int i = 0; i < P[m]; i++)
		if (i > 0 && sector[i] == 0)
			sector[i] = sector[i - 1];
}

inline int sgn(punct A, punct B, punct C) {
	if (A.x > B.x)
		swap(A, B);

	int ans = A.x * B.y + B.x * C.y + C.x * A.y - A.x * C.y - B.x * A.y - C.x * B.y;

	if (ans < 0)
		return -1;
	if (ans > 0)
		return 1;
	return 0;
}

int ans() {
	if (V[Q.x].size()) {
    	set <pair <int, int> >::iterator it = V[Q.x].upper_bound(mp(Q.y, Q.y));
		if (it != V[Q.x].begin()) {
        	--it;
			if (it->first <= Q.y && Q.y <= it->second)
				return 1;
		}
	}

	int ind = sector[Q.x];

	if (ind && E[ind].size()) {
		int L = E[ind].size() - 1, pos = -1;

		for (int i = 9; i >= 0; i--) {
			pos += 1 << i;

			if (pos <= L && sgn(A[E[ind][pos]], A[next(E[ind][pos])], Q) > 0)
				pos += 1 << i;

			pos -= 1 << i;
		}

		if (pos >= 0 && ((L - pos) % 2 == 1 || sgn(A[E[ind][pos]], A[next(E[ind][pos])], Q) == 0))
			return 1;
	}

	return 0;
}

int main() {

	freopen("poligon.in", "r", stdin);
	freopen("poligon.out", "w", stdout);

	scanf("%d %d", &n, &T);
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &A[i].x, &A[i].y);
    	P[i] = A[i].x;
	}

	solve();

	int sol = 0;

	for (int i = 1; i <= T; i++) {
    	scanf("%d %d", &Q.x, &Q.y);
		sol += ans();
	}

	printf("%d\n", sol);

	return 0;
}