Cod sursa(job #346797)

Utilizator savimSerban Andrei Stan savim Data 9 septembrie 2009 18:26:57
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.38 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 810
#define pb push_back

int n, m, sol;
int f[MAX_N], len[MAX_N];

struct punct {
	int x, y;
} v[MAX_N], P;
struct latura {
	double x1, y1, x2, y2;
} l;

vector <latura> A[MAX_N];

void cit() {
	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", &v[i].x, &v[i].y);
		f[i] = v[i].x;
	}

	sort(f + 1, f + n + 1);
}

void intersect(int k) {
	//intersectez latura l cu f[k] si f[k + 1]

	if (l.x1 != l.x2) {
		double m = 1.0 * (l.y2 - l.y1) / (l.x2 - l.x1);
		double n = l.y1 - m * l.x1;

    	l.x1 = f[k];
		l.y1 = (double) m * f[k] + n;

		l.x2 = f[k + 1];
		l.y2 = (double) m * f[k + 1] + n;
	}
	
	A[k].pb(l);
}

inline int cmp(latura P, latura Q) {
	return P.y1 + P.y2 < Q.y1 + Q.y2;
}

void solve() {
	//calculez ce segmente o sa contina muchiile (i, i + 1), 0 < i < k
	v[n + 1] = v[1];
	for (int i = 1; i < n; i++) {
		for (int j = 1; j <= n; j++) {
			l.x1 = v[j].x; l.y1 = v[j].y; 
			l.x2 = v[j + 1].x; l.y2 = v[j + 1].y;

			if (v[j].x > v[j + 1].x || (v[j].x == v[j + 1].x && v[j].y > v[j + 1].y)) {
				l.x1 = v[j + 1].x; l.y1 = v[j + 1].y;
				l.x2 = v[j].x; l.y2 = v[j].y;
			}

            if (f[i] >= l.x1 && f[i + 1] <= l.x2)
				intersect(i);
		}
	}

	for (int i = 1; i < n; i++) {
		sort(A[i].begin(), A[i].end(), cmp);
		len[i] = A[i].size();
	}
}

double det(double x1, double y1, double x2, double y2, double x3, double y3) {
	return (double) x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2;
}

inline int binary_search(int k) {
	int st = -1, dr = len[k], mid = 0, ret = 0;

	while (st + 1 < dr) {
    	mid = (st + dr) / 2;

		double val = det(A[k][mid].x1, A[k][mid].y1, A[k][mid].x2, A[k][mid].y2, P.x, P.y);
		if (val >= 0 && mid > ret) {
        	ret = mid;
			st = val;
		}
		else dr = val;
	}

	return ret % 2;
}

void write() {
	for (int i = 1; i <= m; i++) {
    	scanf("%d %d", &P.x, &P.y);

		int st = 0, dr = n, mid = 0, ok = 0;
		while (st + 1 < dr) {
        	mid = (st + dr) / 2;
			if (f[mid] <= P.x && P.x <= f[mid] + 1) {
            	ok = mid;
				break;
			}
			else if (f[mid] > P.x) dr = mid;
				 else st = mid;
		}

		//caut binar sa vad cate segmente sunt sub punct
		if (ok)
			sol += binary_search(mid);
	}

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

int main() {

	cit();
	solve();
	write();

	return 0;
}