Cod sursa(job #249832)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 29 ianuarie 2009 12:46:29
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include<stdio.h>
#define M 60010
struct nod{int inf;nod *urm;};
nod *in[M],*out[M],*q[M],*paux;
int n,m,i,j,k,a[810],b[810],c[810],d[810],s[810],co[810],lc,lc_aux,
aux,start,stop,aa,bb,left,right,middle,delta,cnt,jos,
det(int a1,int b1,int a2,int b2,int a3,int b3);
void readd(),solve(),add(),deque(),enque(),query();
int main()
{
	readd();
	solve();
	return 0;
}
void readd()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d%d",&n,&m);start=M+10;stop=-1;
	for(i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]);
	for(i=2;i<=n;i++){ c[i]=a[i-1];d[i]=b[i-1];}
	c[1]=a[n];d[1]=b[n];
	a[0]=-1;b[0]=-1;c[0]=M+10;d[0]=-1;
	a[n+1]=-1;b[n+1]=M+10;c[n+1]=M+10;d[n+1]=M+10;
	s[0]=1;s[n+1]=1;
	co[1]=0;co[2]=n+1;lc=2;
	for(i=1;i<=n;i++)
	 if(a[i]>c[i]||(a[i]==c[i]&&b[i]>d[i]))
	  { aux=a[i];a[i]=c[i];c[i]=aux;
	    aux=b[i];b[i]=d[i];d[i]=aux;
	  }
	for(i=1;i<=n;i++)add();
	for(i=1;i<=m;i++)
	{ scanf("%d%d",&aa,&bb);
	  paux=new nod;paux->inf=bb;paux->urm=q[aa];q[aa]=paux;
	}
}
void add()
{
	if(a[i]==c[i])return;
	paux=new nod;paux->inf=i;paux->urm=in[a[i]];in[a[i]]=paux;
	start=(a[i]<start)?a[i]:start;
	paux=new nod;paux->inf=i;paux->urm=out[c[i]];out[c[i]]=paux;
	stop=(c[i]>stop)?c[i]:stop;
}
void solve()
{
	for(i=start;i<=stop;i++)
	{ if(q[i]) query();
	  if(out[i])deque();
	  if(in[i])enque();

	}
	printf("%d\n",cnt);
}
void deque()
{
	for(paux=out[i];paux;paux=paux->urm)s[paux->inf]=2;
	lc_aux=0;
	for(j=1;j<=lc;j++)
	 if(s[co[j]]==1)
	  co[++lc_aux]=co[j];
	lc=lc_aux;
}
void enque()
{
	for(paux=in[i];paux;paux=paux->urm)
	{ left=1;right=lc;j=paux->inf;
	  while(right-left>1)
	  {
		middle=(left+right)/2;
		k=co[middle];
		delta=det(a[k],b[k],c[k],d[k],a[j],b[j]);
		if(!delta)
		delta=det(a[k],b[k],c[k],d[k],c[j],d[j]);
		if(delta>0)left=middle;
		else(right=middle);
	  }
	  for(k=lc+1;k>right;k--)co[k]=co[k-1];
	  co[right]=j;
	  lc++;
	}
}
int det(int a1,int b1,int a2,int b2,int a3,int b3)
{
	return
	a1*b2+a2*b3+a3*b1-b1*a2-b2*a3-b3*a1;
}
void query()
{
	for(paux=q[i];paux;paux=paux->urm)
	{       if(!paux->inf)continue;
		aa=i;bb=paux->inf;
		left=1;right=lc;
		while(right-left>1)
		{
			middle=(left+right)/2;
			k=co[middle];
			delta=det(a[k],b[k],c[k],d[k],aa,bb);
			if(!delta)break;
			if(delta>0)left=middle;
			else right=middle;
		}
		if(!delta){cnt++;paux->inf=0;continue;}
		jos=left-1;
		if(jos&1){cnt++;paux->inf=0;}
	}
}