Cod sursa(job #3810)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 28 decembrie 2006 20:44:48
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

#define nmax 801

int n,m,xp[nmax],yp[nmax],x,y,i,j,sol;

int solve()
{
    int nr=0,i;
	float vld,xx=rand(),yy=1000000;
	for (i=0;i<n;i++)
	{
		vld=(x-xp[i])*(yp[(i+1)%n]-yp[i])-(y-yp[i])*(xp[(i+1)%n]-xp[i]);
		if (vld==0)
			if (((xp[i]<=x)&&(x<=xp[(i+1)%n]))||((xp[i]>=x)&&(x>=xp[(i+1)%n])))
				if (((yp[i]<=y)&&(y<=yp[(i+1)%n]))||((yp[i]>=y)&&(y>=yp[(i+1)%n])))
					return 1;
	}

	for (i=0;i<n;i++)
	{
		vld=(xp[i]-x)*(yy-y)-(yp[i]-y)*(xx-x);
		vld*=(xp[(i+1)%n]-x)*(yy-y)-(yp[(i+1)%n]-y)*(xx-x);
		if (vld==0)
			return solve();
		if (vld<0)
		{
			vld=(x-xp[i])*(yp[(i+1)%n]-yp[i])-(y-yp[i])*(xp[(i+1)%n]-xp[i]);
			vld*=(xx-xp[i])*(yp[(i+1)%n]-yp[i])-(yy-yp[i])*(xp[(i+1)%n]-xp[i]);
            if (vld<0)
                ++nr;
        }
    }
    return (nr%2);
}

int main()
{
    freopen("poligon.in","r",stdin);
    freopen("poligon.out","w",stdout);

    scanf("%d%d",&n,&m);
    for (i=0;i<n;i++)
        scanf("%d%d",xp+i,yp+i);

    sol=0;
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x,&y);
        if (solve())
			++sol;
    }

    printf("%d\n",sol);

    return 0;
}