Cod sursa(job #346676)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 9 septembrie 2009 00:20:06
Problema Poligon Scor 30
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.14 kb
#include <stdio.h>
#include <math.h>

#define Nmax 20010
#define eps 1e-7
#define ll long long

int x[Nmax],y[Nmax],xx,yy;
int i,j,k,N,M,nrm;

int abs(int a)
{
    if (a>0)
         return a;
    return -a;
}

int ecdr(long long a, long long b, long long c, double x, double y)
{
	double d=a*x+b*y+c;

	if (fabs(d)<eps)
        return 0;
	    else
	if (d>0)
		return 1;
	    else
		return -1;
}


int verif(int a, int b, double c)
{
	if (fabs(a-c)<eps || fabs(b-c)<eps || (a<=c && b>=c) || (b<=c && a>=c))
		return 1;
	    else
		return 0;
}

int segm(int xa, int ya, int xb, int yb, double x, double y)
{
	long long a,b,c;

    //calculez panta
	a=ya-yb;
	b=xb-xa;
	c=(long long)(xa)*(long long)(yb)-(long long)(xb)*(long long)(ya);

	return (verif(xa,xb,x) && verif(ya,yb,y) && !ecdr(a,b,c,x,y));
}

int intersectie(int x1a, int y1a, int x1b, int y1b,int x2a, int y2a, int x2b, int y2b)
{
	long long a1, b1, c1, a2, b2, c2;
	double xi,yi;

    //calculez pantele
	a1=y1a-y1b;
	a2=y2a-y2b;
    b1=x1b-x1a;
	b2=x2b-x2a;
    c1=(long long)(x1a)*(long long)(y1b)-(long long)(x1b)*(long long)(y1a);
	c2=(long long)(x2a)*(long long)(y2b)-(long long)(x2b)*(long long)(y2a);

    //sunt paralele
	if (a1*b2==a2*b1)
		return 0;
	else
	{
		xi=(double)(b2*c1-b1*c2)/(double)(a2*b1-a1*b2);
		yi=(double)(c2*a1-c1*a2)/(double)(a2*b1-a1*b2);

		if (segm(x1a,y1a,x1b,y1b,xi,yi) && segm(x2a,y2a,x2b,y2b,xi,yi))
			return 1;
		    else
			return 0;
	}
}

int solve(int xp, int yp)
{
	int np=0;
	int aaa,bbb;

	aaa=90100;
	bbb=yp+10;
	
    for (i=0;i<N;++i)
		if (segm(x[i],y[i],x[i+1],y[i+1],xp,yp))
			return 1;
	for (i=0;i<N;++i)
		np+=intersectie(xp,yp,aaa,bbb,x[i],y[i],x[i+1],y[i+1]);

    //daca e impar e bun
    return np%2==1;
}

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

	scanf("%d %d", &N,&M);
	for (i=0;i<N;++i)
		{
            scanf("%d %d", &x[i], &y[i]);
        }

	x[N]=x[0];
    y[N]=y[0];

    nrm=0;

	for (k=0;k<M;++k)
	{
		scanf("%d %d", &xx, &yy);
		nrm+=solve(xx,yy);
	}

	freopen("poligon.out", "w", stdout);
	printf("%d\n", nrm);


	return 0;
}