Cod sursa(job #616095)

Utilizator ChallengeMurtaza Alexandru Challenge Data 11 octombrie 2011 18:39:14
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 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 cmp_line
{
	inline bool operator() (const line &a, const line &b)
	{
		return a.A.y+a.B.y<b.A.y+b.B.y;
	}
};

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

int N,M;
point p[MaxN];
vector<strip> s;
vector<int> v;

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;
}

int main()
{
	fin>>N>>M;
	v.push_back(MinX);
	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];
	v.push_back(MaxX);
	sort(v.begin(),v.end());
	for(register int i=1;i<=N+1;++i)
	{
		if(v[i-1]==v[i])
		{
			continue;
		}
		strip st;
		st.xmin=v[i-1];
		st.xmax=v[i];
		for(register int i=1;i<=N;++i)
		{
			int xmin=min(p[i].x,p[i+1].x);
			int xmax=max(p[i].x,p[i+1].x);
			if(xmin<=st.xmin && st.xmax<=xmax)
			{
				line l;
				l.A=p[i];
				l.B=p[i+1];
				point UP;
				UP.x=(l.A.x+l.B.x)>>1;
				UP.y=((l.A.y+l.B.y)>>1)+MaxX;
				if(sgn(l.A,l.B,UP)!=WINDING)
				{
					swap(l.A,l.B);
				}
				if(l.A.x!=l.B.x)
				{
					st.l.push_back(l);
				}
			}
		}
		sort(st.l.begin(),st.l.end(),cmp_line());
		s.push_back(st);
	}
	int sol=0;
	for(register int i=1;i<=M;++i)
	{
		int px,py;
		fin>>px>>py;
		point pq;
		pq.x=px; pq.y=py;
		int p=0;
		int u=s.size()-1;
		while(p<=u)
		{
			int m=p+((u-p)>>1);
			if(px<=s[m].xmin)
			{
				u=m-1;
			}
			else
			{
				p=m+1;
			}
		}
		int sind=u;
		if(0<sind && sind<(int)(s.size()-1))
		{
			p=0;
			u=s[sind].l.size()-1;
			while(p<=u)
			{
				int m=p+((u-p)>>1);
				int sg=sgn(s[sind].l[m].A,s[sind].l[m].B,pq);
				if(sg==0)
				{
					++sol;
					goto NEXT;
				}
				if(sg==WINDING)
				{
					p=m+1;
				}
				else
				{
					u=m-1;
				}
			}
			if(u%2==0)
			{
				++sol;
			}
		}
NEXT:
		int a=0;
	}
	fin.close();

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