Cod sursa(job #616391)

Utilizator ChallengeMurtaza Alexandru Challenge Data 12 octombrie 2011 14:42:54
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

const char InFile[]="poligon.in";
const char OutFile[]="poligon.out";
const int MinX=-1;
const int MaxX=60111;
const int MaxN=1024;
const int WINDING=1;

ifstream fin(InFile);
ofstream fout(OutFile);

struct point
{
	int x,y;
};

struct line
{
	point A,B;
};

struct line_sort
{
	line l;
	double mid;
};

struct cmp_line_sort
{
	inline bool operator() (const line_sort &a, const line_sort &b)
	{
		return a.mid<b.mid;
	}
};

struct strip
{
	int xmin,xmax;
	vector<line> l;
};

int N,M,D[MaxN],lind;
line l[MaxN];
point p[MaxN];
vector<int> v;
vector<line_sort> s[MaxN];

inline long long det(const point &a, const point &b, const point &c)
{
	return (long long)(b.x-a.x)*(long long)(c.y-a.y)-(long long)(b.y-a.y)*(long long)(c.x-a.x);
}

inline int sgn(const point &a, const point &b, const point &c)
{
	long long val=det(a,b,c);
	if(val<0)
	{
		return -1;
	}
	else if(val>0)
	{
		return 1;
	}
	return 0;
}

inline double get_y(const line &l, const double &x)
{
	double x1=l.A.x;
	double x2=l.B.x;
	double y1=l.A.y;
	double y2=l.B.y;
	return y2-(x2-x)*(y2-y1)/(x2-x1);
}

inline void build()
{
	sort(v.begin(),v.end());
	D[++D[0]]=v[0];
	for(register unsigned int i=1;i<v.size();++i)
	{
		if(v[i]!=v[i-1])
		{
			D[++D[0]]=v[i];
		}
	}
	D[D[0]+1]=MaxX;

	for(register int i=1;i<=N;++i)
	{
		if(p[i].x!=p[i+1].x)
		{
			++lind;
			l[lind].A=p[i];
			l[lind].B=p[i+1];
			if(l[lind].A.x>l[lind].B.x)
			{
				swap(l[lind].A,l[lind].B);
			}
		}
	}

	line_sort ll;
	ll.l.A.x=50;
	ll.l.A.y=-100;
	ll.l.B.x=100;
	ll.l.B.y=-100;
	ll.mid=-100;

	for(register int i=1;i<D[0];++i)
	{
		for(register int j=1;j<=lind;++j)
		{
			if(l[j].A.x<=D[i] && D[i+1]<=l[j].B.x)
			{
				line_sort tl;
				tl.l=l[j];
				tl.mid=get_y(l[j],(D[i]+D[i-1])*0.5);
				s[i].push_back(tl);
			}
		}
		s[i].push_back(ll);
		sort(s[i].begin(),s[i].end(),cmp_line_sort());
	}
}

inline int search_strip(const int &x)
{
	int first=0;
	int step=1<<10;
	for(;step;step>>=1)
	{
		int index=first+step;
		if(index<D[0] && D[index]<=x)
		{
			first=index;
		}
	}
	return first;
}

inline int search_line(const int &strip, const point &p)
{
	int first=0;
	int step=1<<10;
	for(;step;step>>=1)
	{
		int index=first+step;
		if(index<s[strip].size() && sgn(s[strip][index].l.A,p,s[strip][index].l.B)<=0)
		{
			first=index;
		}
	}
	return first;
}

int main()
{
	fin>>N>>M;
	for(register int i=1;i<=N;++i)
	{
		fin>>p[i].x>>p[i].y;
		v.push_back(p[i].x);
	}
	p[N+1]=p[1];
	
	build();

	int sol=0;
	for(register int i=1;i<=M;++i)
	{
		point pq;
		fin>>pq.x>>pq.y;
		if(pq.x<D[1] || D[D[0]]<pq.x)
		{
			continue;
		}
		int strip=search_strip(pq.x);
		int lp=search_line(strip,pq);
		if(lp%2==1 || sgn(s[strip][lp].l.A,pq,s[strip][lp].l.B)==0)
		{
			++sol;
		}
	}
	fin.close();

	fout<<sol;
	fout.close();
	return 0;
}