Cod sursa(job #776812)

Utilizator darrenRares Buhai darren Data 10 august 2012 14:29:59
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <cmath>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

const double eps = 0.0001;

#define x first
#define y second

int N, aN, M;
pair<int, int> A[802];
int B[802];
int result, onboard;
vector<int> V[802];
int wA[802], wB[802], wC[802];

int xboth1, xboth2;
inline double gety(const int& what, const int& xnow)
{
	return 1.0 * (1.0 * (-wA[what]) * xnow - wC[what]) / wB[what];
}
class sortnow
{
	public: inline bool operator () (const int& i1, const int& i2)
	{
		return (gety(i1, xboth1) + gety(i1, xboth2) < gety(i2, xboth1) + gety(i2, xboth2));
	}
};

inline bool intersect(const int& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
	return (P >= min(p1.x, p2.x) && P < max(p1.x, p2.x));
}
inline bool higher(const pair<int, int>& P, const int& what)
{
	if (1LL * wA[what] * P.x + 1LL * wB[what] * P.y + wC[what] == 0) onboard = 1;
	return (P.y >= gety(what, P.x));
}

int main()
{
	ifstream fin("poligon.in");
	ofstream fout("poligon.out");
	
	fin >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		fin >> A[i].x >> A[i].y;
		B[i] = A[i].x;
	}
	A[N + 1] = A[1];
	
	for (int i = 1; i <= N; ++i)
	{
		wA[i] = (A[i].y - A[i + 1].y);
		wB[i] = (A[i + 1].x - A[i].x);
		wC[i] = (A[i].x * A[i + 1].y - A[i].y * A[i + 1].x);
	}
	
	sort(B + 1, B + N + 1);
	for (int i = 1; i <= N; ++i)
	{
		B[++aN] = B[i];
		while (i < N && B[i] == B[i + 1])
			++i;
	}
	
	for (int i = 1; i <= aN; ++i) // duc din punctul B[i] o verticala
	{
		for (int j = 1; j <= N; ++j)
			if (intersect(B[i], A[j], A[j + 1]))
				V[i].push_back(j);
		
		xboth1 = B[i], xboth2 = B[i + 1];
		sort(V[i].begin(), V[i].end(), sortnow());
	}
	
	pair<int, int> now;
	for (int i = 1; i <= M; ++i)
	{
		fin >> now.x >> now.y;
		if (now.x < B[1] || now.x > B[aN]) continue;
		
		onboard = 0;
		
		int step = 1 << 9, gonow, upped;
		for (gonow = 0; step; step >>= 1)
			if (gonow + step <= aN && B[gonow + step] <= now.x)
				gonow += step;
				
		step = 1;
		for (; step <= V[gonow].size(); step <<= 1);
		
		upped = 0;
		for (; step; step >>= 1)
			if (upped + step <= V[gonow].size())// && higher(now, V[gonow][upped + step - 1]))
				upped += step;
		
		result += max(upped % 2, onboard);
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}