Cod sursa(job #1308538)

Utilizator TiberiuDTiberiu Danciu TiberiuD Data 4 ianuarie 2015 12:50:43
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <fstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
ifstream in("poligon.in");
ofstream out("poligon.out");
 
const double eps = 1e-9;
 
int N, M;
int sol, X, Y;
int banda[801], nrbanda, nowbanda;
double ecm[801], ecn[801];
vector<int> V[801];
bool viz[60001];
 
struct puncte
{
	int x, y;
};
puncte P[801];
 
struct dreapta
{
	int a, b;
	long long c;
};
dreapta Ec[801];
 
double gety(int now, int xnow)
{
	return ecm[now] * xnow / 2.0 + ecn[now];
}
 
bool cmp(int nr1, int nr2)
{
	int xmid = banda[nowbanda] + banda[nowbanda + 1];
	double y1 = gety(nr1, xmid);
	double y2 = gety(nr2, xmid);
 
	return y2 - y1 > eps;
}
 
int GetBanda()
{
	int l = 0, r = nrbanda + 1;
 
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
 
		if (banda[mid] <= X)
			l = mid;
		else
			r = mid;
	}
	return l;
}
 
int solve()
{
	if (X < banda[1] || X > banda[nrbanda])
		return 0;
	int nowbanda = GetBanda();
 
	if (nowbanda == nrbanda)
	{
		if (viz[Y])
			return 1;
		return 0;
	}
 
	int l = -1, r = V[nowbanda].size();
 
	while (r - l > 1)
	{
		int mid = (l + r) / 2;
		int now = V[nowbanda][mid];
		long long det = 1LL * Ec[now].a * X + 1LL * Ec[now].b * Y + Ec[now].c;
 
		if (det == 0)
			return 1;
		if (det > 0)
			l = mid;
		else
			r = mid;
	}
	l += 1;
	if (l & 1)
		return 1;
	return 0;
}
 
int main()
{
	in >> N >> M;
	for (int i = 1; i <= N; ++i)
	{
		in >> P[i].x >> P[i].y;
		banda[i] = P[i].x;
	}
	P[N + 1] = P[1];
 
	sort(banda + 1, banda + N + 1);
	banda[++nrbanda] = banda[1];
	for (int i = 2; i <= N; ++i)
		if (banda[i] != banda[nrbanda])
			banda[++nrbanda] = banda[i];
 
	for (int i = 1; i <= N; ++i)
	{
		if (P[i].x < P[i+1].x)
		{
			Ec[i].a = P[i].y - P[i+1].y;
			Ec[i].b = P[i+1].x - P[i].x;
			Ec[i].c = 1LL * P[i].x * P[i+1].y - 1LL * P[i+1].x * P[i].y;
		}
		else
		{
			Ec[i].a = - P[i].y + P[i+1].y;
			Ec[i].b = - P[i+1].x + P[i].x;
			Ec[i].c = -1LL * P[i].x * P[i+1].y + 1LL * P[i+1].x * P[i].y;
		}
		ecm[i] = -1.0 * Ec[i].a / Ec[i].b;
		ecn[i] = -1.0 * Ec[i].c / Ec[i].b;
	}
 
	for (int i = 1; i <= nrbanda; ++i)
	{
		for (int j = 1; j <= N; ++j)
			if (min(P[j].x, P[j + 1].x) <= banda[i] && banda[i] < max(P[j].x, P[j + 1].x))
				V[i].push_back(j);
		nowbanda = i;
		sort(V[i].begin(), V[i].end(), cmp);
	}
 
	for (int i = 1; i <= N; ++i)
	{
		if (max(P[i].x, P[i + 1].x) == banda[nrbanda])
		{
			if (min(P[i].x, P[i + 1].x) == banda[nrbanda])
			{
				int liminf = min(P[i].y, P[i + 1].y);
				int limsup = max(P[i].y, P[i + 1].y);
 
				for (int j = liminf; j <= limsup; ++j)
					viz[j] = true;
			}
			else if (P[i].x == banda[nrbanda])
				viz[P[i].y] = true;
			else
				viz[P[i + 1].y] = true;
		}
	}
 
	while (M)
	{
		in >> X >> Y;
		sol += solve();
 
		--M;
	}
 
	out << sol << '\n';
 
	return 0;
}