Cod sursa(job #166942)

Utilizator razvi9Jurca Razvan razvi9 Data 28 martie 2008 18:02:52
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
struct{int x1,x2,y1,y2;}s[801];
int x[802],i,j,n,m,y,nr,nx;
vector<int> a[801];
int aux;
inline void swp(int&x,int&y)
{
	aux=x;
	x=y;
	y=aux;
}
int _search(int st,int dr,int what)
{
	if(x[st]>what || x[dr]<what || st==dr) return 0;
	int mij=(st+dr)>>1;
	if(what>=x[mij] && what<=x[mij+1]) return mij;
	if(what<x[mij]) return _search(st,mij-1,what);
	else return _search(mij+1,dr,what);
}
inline int under(int k,int x,int y)
{
	int x1=s[k].x1,x2=s[k].x2,y1=s[k].y1,y2=s[k].y2;
	int d=x1*y2+x2*y+x*y1-x2*y1-x*y2-x1*y;
	if(d<0) return 1;
	if(d==0) return 2;
	return 0;
}
inline int countunder(int k,int x,int y)
{
	int nr=0,i,j;
	for(i=0;i<a[k].size();i++){
		j=under(a[k][i],x,y);
		if(j==2) return 1;
		if(j) nr++;}
	return nr;
}
int main()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d %d",&n,&m);
	scanf("%d %d",&x[1],&y);
	s[1].x1=x[1];
	s[1].y1=y;
	s[n].x2=x[1];
	s[n].y2=y;
	for(i=2;i<=n;i++){
		scanf("%d %d",&x[i],&y);
		s[i].x1=x[i];
		s[i].y1=y;
		s[i-1].x2=x[i];
		s[i-1].y2=y;
		if(s[i-1].x1>s[i-1].x2) {swp(s[i-1].x1,s[i-1].x2);swp(s[i-1].y1,s[i-1].y2);}	}
	if(s[n].x1>s[n].x2) {swp(s[n].x1,s[n].x2);swp(s[n].y1,s[n].y2);}
	sort(&x[1],&x[n+1]);
	i=1;j=1;
	while(j<n){
		while(x[i]==x[j+1] && j<n) j++;
		if(j==n)break;
		if(j-i!=0)
			x[++i]=x[++j];}
	nx=i;
	i=1;j=1;
	while(j<n){
		while(s[j].x1==s[j].x2&&j<=n) j++;
		if(i==j) while(s[j].x1!=s[j].x2&&j<=n) i++,j++;
		else
			while(s[j].x1!=s[j].x2&&j<=n)
				s[i++]=s[j++];}
	n=i-1;
	for(i=1;i<=n;i++){
		y=_search(1,nx-1,s[i].x1);
		for(;y<nx&&x[y]<=s[i].x2;y++)
			a[y].push_back(i);}
	n--;
	for(i=1;i<=m;i++){
		scanf("%d %d",&x[0],&y);
		j=_search(1,nx,x[0]);
		if(!j) continue;
		j=countunder(j,x[0],y);
		if(j%2) nr++;}
	printf("%d\n",nr);
	fclose(stdout);
	return 0;
}