Cod sursa(job #708560)

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

int interior(poligon M)
{
	int i,intersectii;
	double t,cy;
	
	p[n+1]=p[1];
	
	for(i=1;i<=n;++i)
	{
		if((p[i].x<M.x&&M.x<p[i+1].x)||(p[i].x>M.x&&M.x>p[i+1].x))
		{
			t=(M.x-p[i+1].x)/(p[i+1].x-p[i+1].x);
			cy=t*p[i].y+(1-t)*p[i+1].y;
			if(M.y==cy)
				return 1;
			if(M.y>cy)
				++intersectii;
		}
		
		if(p[i].x==M.x&&p[i].y>=M.y&&p[i+1].y<=M.y)
			return 1;
		
		if(p[i].x==M.x&&p[i].y<=M.y)
		{
			if(p[i].y==M.y)
				return 1;
			if(p[i+1].x==M.x)
			{
				if((p[i].y<=M.y&&M.y<=p[i+1].y)||(p[i].y>=M.y&&M.y>=p[i+1].y))
					return 1;
			}
			else
				if(p[i+1].x>M.x)
					++intersectii;
				if(p[i-1].x>M.x)
					++intersectii;
		}
	}
	if(intersectii%2)
		return 1;
	else
	return 0;
}

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);
		printf("%d\n",interior(a));
		//if(interior(a))
			++nr;
	}
	
	printf("%d\n",nr);
	return 0;
}