Cod sursa(job #2407448)

Utilizator LucaSeriSeritan Luca LucaSeri Data 16 aprilie 2019 21:16:48
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <bits/stdc++.h>
 
using namespace std;

const int MAXN = 810;

int x[MAXN];
int y[MAXN];

/// y1 + dx / dy * (x-x1) > y2 + dx / dy *(x-x1)
long double eval(int i, long double xx) {
	if(x[i] == x[i+1]) return min(y[i], y[i+1]);
	if(y[i] == y[i+1]) return y[i];
	return 1.0*y[i] + ((1.0*x[i+1]-1.0*x[i])/(1.0*y[i+1]-1.0*y[i]))*(1.0*xx-1.0*x[i]);
}

bool intre(int a, int b, int c) {
	if(a > b) swap(a, b);
	return c >= a && c <= b;
}
bool collinear(int i, int xx, int yy) {
	return (1.0*(1.0*yy-1.0*y[i])*1.0*(1.0*x[i+1]-1.0*x[i]) == 1.0*(1.0*y[i+1]-1.0*y[i])*1.0*(1.0*xx-1.0*x[i])) && intre(x[i], x[i+1], xx) && intre(y[i], y[i+1], yy);
}

int main() {
	#ifdef BLAT
		freopen("input", "r", stdin);		
	#else
		freopen("poligon.in", "r", stdin);
		freopen("poligon.out", "w", stdout);
	#endif	

	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	srand(time(nullptr));

	int n, m;
	cin >> n >> m;

	vector< int > startFasii;
	startFasii.emplace_back(1e9);
	for(int i = 0; i < n; ++i) {
		cin >> x[i] >> y[i];
		startFasii.emplace_back(x[i]);
	}

	x[n] = x[0];
	y[n] = y[0];

	sort(startFasii.begin(), startFasii.end());
	startFasii.erase(unique(startFasii.begin(), startFasii.end()), startFasii.end());

	vector< vector< int>  > interest(startFasii.size() + 1);

	for(int i = 0; i < startFasii.size() - 1; ++i) {
		for(int j = 0; j < n; ++j) {
			int x1 = x[j], x2 = x[j+1];
			if(x2 < x1) swap(x1, x2);

			if(x1 <= startFasii[i] && x2 >= startFasii[i]) {
				interest[i].emplace_back(j);
				if(x1 == x2) interest[i].emplace_back(j);
			}
		}
	}

	for(int i = 0; i < startFasii.size(); ++i) {
		sort(interest[i].begin(), interest[i].end(), [&](int a, int b) -> bool {
			return eval(a, startFasii[i] + 0.5) < eval(b, startFasii[i] + 0.5);
		});
	}

	int ans = 0;

	// for(int i = 0; i < startFasii.size(); ++i) {
	// 	cout << i << ' ' << startFasii[i] << ' ';
	// 	for(auto &x : interest[i]) cout << x << ' ';
	// 	cout << '\n';
	// }

	const long double eps = 1e-8;
	for(int i = 0; i < m; ++i) {
		int xx, yy;
		cin >> xx >> yy;
		int fasie = 0; 
		for(int step = 20; step >= 0; --step) {
			if(fasie + (1<<step) < startFasii.size() && startFasii[fasie+(1<<step)] <= xx) {
				fasie += (1<<step);
			}
		}
		if(xx < startFasii[0]) continue;
		// cout << xx << ' ' << yy << " e pe fasia " << fasie << '\n';
		int where = -1;
		bool ok = false;
		for(int step = 20; step >= 0; --step) {
			if(where + (1<<step) < interest[fasie].size()) {
				if(collinear(interest[fasie][where+(1<<step)], xx, yy)) {
					ok = true;
				}
				if(eval(interest[fasie][where+(1<<step)], xx) < 1.0*yy + eps) {
					where += (1<<step);
				}
			}
		}
		// cout << i << ' ' << where << '\n';
		if(ok || (where%2==0)) {
			// cout << i << '\n';
			ans ++;
		}
	} 

	cout << ans << '\n';
    return 0;	
}