Cod sursa(job #346968)

Utilizator savimSerban Andrei Stan savim Data 10 septembrie 2009 14:20:54
Problema Poligon Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.24 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 810

int n, m, t, sol;
int f[MAX_N], len[MAX_N];
int prec[60010];
double dm, dn;

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

struct latura {
	double y1, y2;
};
vector <latura> v[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", &A[i].x, &A[i].y);
	A[n + 1] = A[1];

	//gasesc numarul de fasii
	for (int i = 1; i <= n; i++) f[i] = A[i].x;
	
	sort(f + 1, f + n + 1);
	
	t = 1;
	for (int i = 1; i < n; i++)
		if (f[i] != f[i + 1]) 
			f[++t] = f[i + 1];

	//precalculez prima fasie inainte de pozitia i
	for (int i = 1; i < t; i++)
		prec[f[i]] = i;
	for (int i = 0; i <= 60000; i++)
		if (!prec[i]) prec[i] = prec[i - 1];
}

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

void solve() {
	for (int i = 1; i <= n; i++) 
    	if (A[i].x != A[i + 1].x) { //am luat o latura i
			dm = 1.0 * (A[i + 1].y - A[i].y) / (A[i + 1].x - A[i].x);
			dn = A[i].y - dm * A[i].x;

			for (int j = 1; j < t; j++)
				if ((A[i].x <= f[j] && f[j + 1] <= A[i + 1].x) || (A[i + 1].x <= f[j] && f[j + 1] <= A[i].x)) {
                	//intersectez fasiile (f[j], f[j + 1]) cu latura (j, j + 1)
                	latura lat;
					lat.y1 = dm * f[j] + dn;
					lat.y2 = dm * f[j + 1] + dn;

					v[j].push_back(lat);
					len[j]++;
				}
		}

	for (int i = 1; i < t; i++)
		if (len[i])
			sort(v[i].begin(), v[i].end(), cmp);
}

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

void binary_search(int k) {
	int st = -1, dr = len[k], mid = 0, poz = -1;
	while (st + 1 < dr) {
    	mid = (st + dr) / 2;                                                    

		double val = det(f[k], v[k][mid].y1, f[k + 1], v[k][mid].y2, P.x, P.y);

		if (val == 0) {
        	sol++;
			return;
		}
		if (val > 0) {
        	if (mid > poz) poz = mid;
			st = mid;
		}
		else dr = mid;
	}

	sol += (poz + 1) % 2;
}

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

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

int main() {

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

	return 0;
}