Cod sursa(job #326540)

Utilizator tvladTataranu Vlad tvlad Data 25 iunie 2009 15:22:55
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

struct Point { int x, y; };
bool operator< ( const Point &a, const Point &b ) { return a.y < b.y; } // comparare pe verticala

struct Segment { Point a,b; };
bool operator< ( const Segment &a, const Segment &b ) {
	Point a1 = min(a.a, a.b), a2 = max(a.a, a.b);
	Point b1 = min(b.a, b.b), b2 = max(b.a, b.b);
	return (a1 < b1) ? true :
		(b1 < a1) ? false :
		(a2 < b2) ? true : false;
}
inline double XtoY ( const Segment &a, int x ) {
	int dx = a.a.x - a.b.x;
	int dy = a.a.y - a.b.y;
	int z = x - a.a.x;
	return a.a.y + (double)(dy*z)/dx;
}
inline bool segOnX ( const Segment &a, int x1, int x2 ) {
	int xmin = min(a.a.x, a.b.x), xmax = max(a.a.x, a.b.x);
	return xmin <= x1 && xmax >= x2;
}
bool operator< ( const Segment &s, const Point &p ) { return XtoY(s,p.x) <= p.y; }
bool operator< ( const Point &a, const Segment &b ) { return !(b < a); }

struct Lane { int xStart, xEnd; vector<Segment> S; };
bool operator< ( const Lane &a, const Lane &b ) { return a.xStart < b.xStart; }
bool operator< ( const Lane &a, const int &b ) { return a.xEnd < b; }
bool operator< ( const int &a, const Lane &b ) { return !(b < a); }

const int N_MAX = 800;

int n, q, m;
Point v[N_MAX];
Segment sv[N_MAX];
Lane lv[N_MAX];

int main() {
	freopen("poligon.in","rt",stdin);
	freopen("poligon.out","wt",stdout);
	scanf("%d %d",&n,&q);
	vector<int> aux;
	for (int i = 0; i < n; ++i) {
		scanf("%d %d",&v[i].x,&v[i].y);
		aux.push_back(v[i].x);
	}
	for (int i = 0; i < n; ++i) {
		sv[i].a = v[i];
		sv[i].b = v[(i+1) % n];
	}
	sort(aux.begin(),aux.end());
	int m = unique(aux.begin(), aux.end()) - aux.begin();
	aux.resize(m);
	for (int i = 0; i < m-1; ++i) {
		lv[i].xStart = aux[i];
		lv[i].xEnd = aux[i+1];
		for (int j = 0; j < n; ++j) {
			if (segOnX(sv[j], lv[i].xStart, lv[i].xEnd)) {
				lv[i].S.push_back(sv[j]);
			}
		}
		sort(lv[i].S.begin(), lv[i].S.end());
	}

	int ans = 0;
	for (int i = 0; i < q; ++i) {
		Point qp;
		scanf("%d %d",&qp.x,&qp.y);
		int zona = lower_bound(lv,lv+m-1,qp.x) - lv;
		if (zona >= m-1 || lv[zona].xStart > qp.x) continue;
		int h = lower_bound(lv[zona].S.begin(), lv[zona].S.end(), qp) - lv[zona].S.begin();
		fprintf(stderr,"Punctul (%d,%d) este deasupra a %d segmente\n",qp.x,qp.y,h);
		if (h & 1)
			++ans;
	}
	printf("%d\n",ans);
	return 0;
}