Cod sursa(job #48047)

Utilizator pocaituDavid si Goliat pocaitu Data 4 aprilie 2007 12:59:15
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<stdio.h>
#define lm 2
#define mm 60100
#define nm 802
int n,m,nr;
struct {int x,y;} p[nm],inf[mm];
inline int maxim(int a,int b) {return a>b?a:b;}



void readdata()
{int i,j;

freopen("poligon.in","r",stdin);
 scanf("%d%d",&n,&m);
 for(i=0;i<n;i++)
  scanf("%d%d",&p[i].x,&p[i].y);
 for(i=1;i<=m;i++)
   scanf("%d%d",&inf[i].x,&inf[i].y);
 }



int resp(int i,int j)
{
 if(maxim(p[j].x,p[j+1].x)>=inf[i].x)
	return 0;
 return 1;
 }



int inter(int i,int j)
{long pr1,pr2,d;

 if(p[j].x>=inf[i].x&&p[j].y==inf[i].y)
		 {d=-1;
		  pr1=(p[j+d].x-inf[i].x)*(p[j].y-inf[i].y)-(p[j+d].y-inf[i].y)*(p[j].y-inf[i].y);
		  d=1;
		  pr2=(p[j+d].x-inf[i].x)*(p[j].y-inf[i].y)-(p[j+d].y-inf[i].y)*(p[j].y-inf[i].y);
		  if(pr1*pr2>=0)
			return 0;
		  else
			return 1;
		  }
	   if(p[j+1].x>=inf[i].x&&p[j+1].y==inf[i].y)
		 return 0;

	   if(resp(i,j))
		 return 0;
	   pr1=(p[j].x-inf[i].x)*0-(p[j].y-inf[i].y)*lm;
	   pr2=(p[j+1].x-inf[i].x)*0-(p[j+1].y-inf[i].y)*lm;
	   if(pr1*pr2>0)
		  return 0;
	   /*pr1=(inf[i].x-p[j].x)*(p[j+1].y-p[j].y)-(inf[i].y-p[j].y)*(p[j+1].y-p[j].y);
	   pr2=(inf[i].x+lm-p[j].x)*(p[j+1].y-p[j].y)-(inf[i].y-p[j].y)*(p[j+1].y-p[j].y);
	   if(pr1*pr2>0)
		 return 0;*/
	   return 1;
}



void solve()
{int adev=0,i,j;

 p[n].x=p[0].x;
 p[n].y=p[0].y;
 for(i=1;i<=m;i++)
  {adev=0;
   for(j=0;j<n;j++)
		adev+=inter(i,j);
   if(adev%2)
	 nr++;
   }

 }
void printdata()
{
 freopen("poligon.out","w",stdout);
  printf("%d",nr);
  fclose(stdout);
  }
int main()
{

 readdata();
 solve();
 printdata();

 return 0;
 }