Cod sursa(job #597220)

Utilizator savimSerban Andrei Stan savim Data 21 iunie 2011 14:24:24
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.76 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 810

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

int P[MAX_N], stop[MAX_N];

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

struct edge {
	int x;
	double l, r;
} E[2 * MAX_N], V[MAX_N];

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

inline bool cmp_V(const edge &A, const edge &B) {
	if (A.x != B.x)
		return A.x < B.x;
	else
		return A.l < B.l;
}

inline bool cmp_E(const edge &A, const edge &B) {
	if (P[A.x] != P[B.x])
		return P[A.x] < P[B.x];
	else
		return A.l + A.r < B.l + B.r;
}

void solve() {
	sort(P + 1, P + n + 1); P[0] = -1;
	for (int i = 1; i <= n; i++)
		if (P[i] != P[i - 1])
			P[++k] = P[i];
	
	for (int i = 1; i <= n; i++) 
		if (A[i].x == A[next(i)].x) {
			V[++nrV].x = A[i].x;
			V[nrV].l = min(A[i].y, A[next(i)].y); //numarul de laturi verticale
			V[nrV].r = max(A[i].y, A[next(i)].y);
		}
		else
	    	for (int j = 1; j < k; j++) //sectionez latura i, next(i) 
				if (min(A[i].x, A[next(i)].x) <= P[j] && P[j + 1] <= max(A[i].x, A[next(i)].x)) {
            		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;

					E[++nrE].x = j;
					E[nrE].l = m * min(A[i].x, A[next(i)].x) + n;
					E[nrE].r = m * max(A[i].x, A[next(i)].x) + n;
				}
	
	sort(V + 1, V + nrV + 1, cmp_V);

	for (int i = 1; i < k; i++) { 
    	E[++nrE].x = i;
    	E[nrE].l = E[nrE].r = -1;
	}

	sort(E + 1, E + nrE + 1, cmp_E); 

	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= nrE; j++)
			if (E[j].x == i) 
				stop[i] = j;
}

inline int sgn(int x1, double y1, int x2, double y2, int x3, int y3) {
	double ans = x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;

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

int ans() {
    //caut in V
	int pos = 0;
	for (int i = 9; i >= 0; i--) {
    	pos += 1 << i;

		if (pos <= nrV && ((V[pos].x < Q.x) || (V[pos].x == Q.x && V[pos].l <= Q.y)))
			pos += 1 << i;

		pos -= 1 << i;
	}

	if (V[pos].x == Q.x && V[pos].l <= Q.y && Q.y <= V[pos].r)
		return 1;

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

		if (pos <= nrE && 
			(P[E[pos].x + 1] < Q.x || (P[E[pos].x] <= Q.x && sgn(P[E[pos].x], E[pos].l, P[E[pos].x + 1], E[pos].r, Q.x, Q.y) >= 0)))
			pos += 1 << i;
    
		pos -= 1 << i;
	}

	if ((stop[E[pos].x] - pos) % 2 == 1 || sgn(P[E[pos].x], E[pos].l, P[E[pos].x + 1], E[pos].r, Q.x, Q.y) == 0)
		return 1;

	return 0;
}

int main() {

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

	scanf("%d %d", &n, &m);
	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 <= m; i++) {
    	scanf("%d %d", &Q.x, &Q.y);
		sol += ans();
	}

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

	return 0;
}