Cod sursa(job #1736838)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 2 august 2016 19:05:33
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

#define point pair<int, int>
#define pointd pair<double, double>
#define x first
#define y second

const int NMAX = 803;//nr vf-uri poligon
const int MMAX = 60009; //nr puncte
const int INF = 60009;

int n; int m;

point pol[NMAX];
point v[MMAX];

struct Segment {

	double a; double b; double c;
	pointd middle;
	pointd p1;
	pointd p2;

	Segment(point _p1, point _p2) {
		p1 = _p1;
		p2 = _p2;
		a = p1.y - p2.y;
		b = p2.x - p1.x;
		c = p1.x * p2.y - p1.y * p2.x;

		middle = pointd( (p1.x + p2.x) * 0.5, (p1.y + p2.y) * 0.5);
	}

	bool operator<(Segment s) const {
		return middle.y < s.middle.y; //segmentele nu se intersecteaza 
	}
};

struct Sector {

	int inf; int sup;
	vector<Segment> seg;
};

Sector s[NMAX]; int cnt;

int f[INF];

void read() {

	fin >> n >> m;
	for(int i = 1; i <= n; ++i)
		fin >> pol[i].x >> pol[i].y;

	for(int i = 1; i <= m ; ++i)
		fin >> v[i].x >> v[i].y;
}


double det(point p1, point p2, point p3) {

	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

int sgn(Segment seg, point p) {

	return det(seg.p1, seg.p2, p) < 0 ? -1 : 1;
}

int findSector(point p) {

	int pos = 0 ; int step ;
	for( step = 1; step <= cnt; step <<= 1);

	for(pos = 0; step ; step >>= 1)
		if(pos + step < cnt && s[pos + step].sup < p.x)
			pos += step;

	return pos + 1;
}

int count(Sector sector, point p) {

	int pos; int step;
	for(step = 1; step < sector.seg.size(); step <<=1 );

	for(pos = 0; step ; step >>= 1)
		if(pos + step < sector.seg.size() 
			&& sgn(sector.seg[pos + step], p) == -1)
			pos += step;
	return pos;
}

pointd intersection(int coordx, Segment seg) {

	pointd p;
	p.x = coordx;
	p.y = 1.0 * (-seg.c - seg.a * coordx) / seg.b;
	return p;
}

void solve() {

	
	for(int i = 1 ; i <= n; ++i)
		f[pol[i].x] = 1;

	int start;

	if(f[0] == 1)
		start = 0;
	else {
		start = 1;
		s[++cnt].inf = 0;
	}

	for(int i = start ; i < INF; ++i)
		if(f[i])
			s[++cnt].inf = i;

	for(int i = 1; i < cnt; ++i)
		s[i].sup = s[i + 1].inf;

	s[cnt].sup = INF;

	//for(int i = 1; i <= cnt; ++i)
	//	cout << s[i].inf << ' ' << s[i].sup << '\n';

	pol[n + 1] = pol[1];

	for(int i = 1; i <= cnt; ++i) {
		//fiecare fasie
		for(int j = 1; j <= n ; ++j) { //segment

			if( (pol[j].x <= s[i].inf && s[i].sup <= pol[j + 1].x) ||
			    (pol[j + 1].x <= s[i].inf && s[i].sup <= pol[j].x) ) {

				//cout << s[i].inf << ' ' << s[i].sup << ' ' << pol[j].x << 
			    //' ' << pol[j].y << ' ' <<  pol[j + 1].x  << ' ' << pol[j + 1].y << '\n';
				
				Segment seg = Segment(pol[j], pol[j + 1]);

				pointd inter1 = intersection(s[i].inf, seg);
				pointd inter2 = intersection(s[i].sup, seg);
				s[i].seg.push_back(Segment(inter1, inter2));
			}
		}

		sort(s[i].seg.begin(), s[i].seg.end());
	}


	int nrPoints = 0;
	/*
	for(int i = 1; i <= cnt; ++i)
		for(Segment seg : s[i].seg)
			cout << seg.p1.x << ' ' << seg.p1.y << ' ' << seg.p2.x << ' ' << seg.p2.y << '\n' << seg.middle.y << '\n';
	*/
	for(int i = 1; i <= m; ++i) {

		int sec = findSector(v[i]);
		if(count(s[sec], v[i]) % 2)
			nrPoints++;
	}

	fout << nrPoints << '\n';

}

int main() {

	read(); solve();
	return 0;
}