Cod sursa(job #776786)

Utilizator darrenRares Buhai darren Data 10 august 2012 13:54:04
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 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, M;
pair<int, int> A[802];
pair<int, int> B[802];
int result, onboard;
vector<int> V[802], W[802];

int xboth;
inline double gety(const int& what)
{
	int a = (A[what].y - A[what + 1].y), b = (A[what + 1].x - A[what].x), c = (A[what].x * A[what + 1].y - A[what].y * A[what + 1].x);
	
	return 1.0 * (1LL * (-a) * xboth - c) / b;
}
inline double gety(const int& what, int xnow)
{
	int a = (A[what].y - A[what + 1].y), b = (A[what + 1].x - A[what].x), c = (A[what].x * A[what + 1].y - A[what].y * A[what + 1].x);
	
	return 1.0 * (1LL * (-a) * xnow - c) / b;
}
class sortnow
{
	public: inline bool operator () (const int& i1, const int& i2)
	{
		if (fabs(gety(i1) - gety(i2)) > eps)
			return gety(i1) < gety(i2);
		
		int add = (max(A[i1].x, A[i1 + 1].x) != xboth ? 1 : -1);
		return (gety(i1, xboth + add) < gety(i2, xboth + add));
	}
};

inline bool intersect(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
	return (P.x >= min(p1.x, p2.x) && P.x < max(p1.x, p2.x));
}
inline bool intersect2(const pair<int, int>& P, const pair<int, int>& p1, const pair<int, int>& p2)
{
	return (P.x > min(p1.x, p2.x) && P.x <= max(p1.x, p2.x));
}
inline bool higher(const pair<int, int>& P, int what)
{
	int a = (A[what].y - A[what + 1].y), b = (A[what + 1].x - A[what].x), c = (A[what].x * A[what + 1].y - A[what].y * A[what + 1].x);
	if (1LL * a * P.x + 1LL * b * P.y + c == 0) onboard = 1;
	
	double ypoint = 1.0 * (1LL * (-P.x) * a - c) / b;
	return (P.y >= ypoint);
}

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];
	}
	A[N + 1] = A[1];
	
	sort(B + 1, B + N + 1);
	
	for (int i = 1; i <= N; ++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);
			if (intersect2(B[i], A[j], A[j + 1]))
				W[i].push_back(j);
		}
		xboth = B[i].x;
		sort(V[i].begin(), V[i].end(), sortnow());
		sort(W[i].begin(), W[i].end(), sortnow());
	}
	
	pair<int, int> now;
	for (int i = 1; i <= M; ++i)
	{
		fin >> now.x >> now.y;
		onboard = 0;
		
		int step = 1 << 9, gonow, upped, addnow = 0;
		for (gonow = 0; step; step >>= 1)
			if (gonow + step <= N && B[gonow + step].x <= now.x)
				gonow += step;
		
		step = 1;
		for (; step <= W[gonow].size(); step <<= 1);
		
		upped = 0;
		for (; step; step >>= 1)
			if (upped + step <= W[gonow].size() && higher(now, W[gonow][upped + step - 1]))
				upped += step;
		
		addnow = max(addnow, upped % 2);
		
		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;
		
		addnow = max(addnow, upped % 2);
		addnow = max(addnow, onboard);
		result += addnow;
	}
	
	fout << result << '\n';
	
	fin.close();
	fout.close();
}