Cod sursa(job #564248)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 26 martie 2011 23:13:41
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
#define nmax 810
#define mp make_pair
#define eps 0.00000001
#define inf 70000
#define f first
#define s second

int n, m, x[nmax], y[nmax], a[nmax], l, sol;
set <pair <int, pair<int, int> > > s;
vector <int> v[nmax];
double mx;

double gety(int i, double mx)
{	
	return (double) (mx*(y[i+1]-y[i])+y[i]*x[i+1]-x[i]*y[i+1])/(x[i+1]-x[i]);
}

int cmp(int i, int j)
{
	return gety(i, mx)<gety(j, mx);
}

int isInside(int i, int x, int y)
{
	int a, b, m, r=-1;
	a=0;
	b=v[i].size()-1;
	while (a<=b)
	{
		m=(a+b)/2;
		if (gety(v[i][m], x)<=y)
		{
			r=m;
			a=m+1;
		} else b=m-1;
	}
	if (r>=0 && fabs(gety(v[i][r], x)-y)<=eps) return 1;
	if (r+1<v[i].size() && fabs(gety(v[i][r+1], x)-y)<=eps) return 1;
	if (r%2) return 0; else return 1;
}
	

int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d %d", &n, &m);
	int i, j, xx, yy;
	for (i=1; i<=n; i++) 
	{
		scanf("%d %d", &x[i], &y[i]);
		a[i]=x[i];
	}
	x[n+1]=x[1];
	y[n+1]=y[1];
	sort(a+1, a+n+1);
	l=0;
	a[0]=-1;
	for (i=1; i<=n; i++)
		if (a[i]!=a[i-1]) a[++l]=a[i];
	for (i=1; i<=n; i++) s.insert(mp(x[i], mp(y[i], y[i])));
	for (i=1; i<=l; i++)
		for (j=1; j<=n; j++)
		{
			if (i<l)
				if ((x[j]<=a[i] && x[j+1]>=a[i+1]) || (x[j+1]<=a[i] && x[j]>=a[i+1])) v[i].push_back(j);
			if (x[j]==x[j+1] && x[j]==a[i])
				s.insert(mp(x[j], mp(min(y[j], y[j+1]), max(y[j], y[j+1]))));
		}
	for (i=1; i<l; i++) 
	{
		mx=(a[i]+a[i+1])/2;
		sort(v[i].begin(), v[i].end(), cmp);
	}
	
	set<pair<int, pair<int, int> > >::iterator it;
	while (m--)
	{
		scanf("%d %d", &xx, &yy);
		int j=upper_bound(a+1, a+l, xx) - 1 -a;
		if (isInside(j, xx, yy)) sol++; else
			if (a[j]==xx)
			{
				it=s.upper_bound(mp(xx, mp(yy, inf)));
				if (it!=s.begin())
				{
					it--;
					if ((*it).f==xx && (*it).s.f<=yy && (*it).s.s>=yy) sol++;
				}
			}
	}
	printf("%d\n",sol);
}