Cod sursa(job #346822)

Utilizator savimSerban Andrei Stan savim Data 9 septembrie 2009 19:31:00
Problema Poligon Scor 70
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.41 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_N 810
#define pb push_back

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

struct punct {
	int x, y;
} v[MAX_N], P;
struct latura {
	int x1, x2;
	double y1, 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);

	f[t = 1] = f[1];
	for (int i = 1; i < n; i++)
		if (f[i] != f[i + 1])
			f[++t] = f[i + 1];
}

void intersect(int k) {
	//intersectez latura l cu f[k] si f[k + 1]
	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 < t; 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 (l.x1 != l.x2 && f[i] >= l.x1 && f[i + 1] <= l.x2)
				intersect(i);
		}
	}

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

	for (int i = 0; i <= 60000; i++)
		if (!prec[i]) prec[i] = prec[i - 1];
}

inline double det(int x1, double y1, int x2, double y2, int x3, int y3) {
	return (double) 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;
	int ret = -1;

	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) {
			sol++;
			return;
		}

		if (val > 0) {
			if (mid > ret)
	        	ret = mid;
			st = mid;
		}
		else dr = mid;
	}

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

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

		//caut binar sa vad cate segmente sunt sub punct
		if (prec[P.x]) binary_search(prec[P.x]);
	} 

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

int main() {

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

	return 0;
}