Cod sursa(job #49421)

Utilizator lucibitLucian Onea lucibit Data 5 aprilie 2007 19:15:37
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
#define inf 60001
long int n,m,xp[801],yp[801];
int poli(long int x,long int y)
{int i,j,k,ok;
 ok=0;
 long a,b;
 for(i=1,j=n;i<=n;j=i++)
	{ a=-(inf-x)*(yp[i]-y);
	  b=-(inf-x)*(yp[j]-y);
		if((a<=0 && b>=0)||(a>=0 && b<=0)) {a=(x-xp[i])*(yp[j]-yp[i])-(y-yp[i])*(xp[j]- xp[i]);
														b=(inf-xp[i])*(yp[j]-yp[i])-(y-yp[i])*(xp[j]- xp[i]);
														if((a<=0 && b>=0)||(a>=0 && b<=0)) ok=!ok;
														}
	 }
 return ok;
 }

int main ()
{long int i,x,y,NR;
 freopen("poligon.in","r",stdin);
scanf("%ld %ld\n",&n,&m);
for(i=1;i<=n;i++) scanf("%ld %ld\n",&xp[i],&yp[i]);
NR=0;
for(i=1;i<=m;i++)
{scanf("%ld %ld\n",&x,&y);
 if(poli(x,y)) NR++;
 }
 freopen("poligon.out","w",stdout);
 printf("%ld\n",NR);
return 0; }