Cod sursa(job #708581)

Utilizator valentina506Moraru Valentina valentina506 Data 6 martie 2012 22:31:11
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include<fstream>
using namespace std;
int n,m,i,j,nr;
struct poligon
{
	double x,y;
};
poligon P[810],a;

inline int interior(double x, double y)
{
    int i,inters=0; 
	double cy,t;

    for(i=1;i<=n;++i)
	{

        if((P[i].x<x&&x<P[i+1].x)||(P[i].x>x&&x>P[i+1].x))
		{
            t=(x-P[i+1].x)/(P[i].x-P[i+1].x);
            cy =t*P[i].y+(1-t)*P[i+1].y;
            if(y==cy) 
				return 1; 
            if(y>cy) 
				inters++;
        }

        if(P[i].x==x)
		{
            if(P[i].y==y) 
				return 1;
            if(P[i+1].x==x)
			{
                if((P[i].y <=y && y<=P[i+1].y) || ( P[i].y>=y && y>=P[i+1].y ) )
                    return 1;
            }
            else{
                if(P[i].y>y) 
					continue;
                if((P[i+1].x>x&&P[i-1].x<x)||(P[i+1].x<x&&P[i-1].x>x))
                    inters++;
            }
        }
    }
    return inters%2;
}


int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=n;++i)
		scanf("%lf %lf ",&P[i].x,&P[i].y);
	for(i=1;i<=m;++i)
	{
		scanf("%lf%lf",&a.x,&a.y);
		if(interior(a.x,a.y))
			++nr;
	}
	
	printf("%d\n",nr);
	return 0;
}