Cod sursa(job #346662)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 septembrie 2009 21:54:44
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
typedef pair<int,int> punct;
struct dreapta{ int a,b,c; };
const int NMAX=808;
int N,M;
punct P[NMAX];
dreapta D[NMAX];
vector<int> Banda[NMAX],nx;
vector< pair<double,int> > nB;
pair<double,int> compute(int iD,int x,int y)
{
	double a=D[iD].a,b=D[iD].b,c=D[iD].c;
	return mp(0.5*((double)y - (a*x+c)/b) , iD);
}
int semn(int iD,int x,int y)
{
	int ret = D[iD].a*x + D[iD].b*y + D[iD].c;
	//fprintf(stderr,"semn %d %d %d %d %d\n",iD,D[iD].a,D[iD].b,D[iD].c,ret);
	if (ret > 0) return 1;
	if (ret == 0) return 0;
	return -1;
}
int main()
{
	int i,j,sol=0;
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d %d",&N,&M);
	for (i=1;i<=N;++i) scanf("%d %d",&P[i].x,&P[i].y);
	P[N+1]=P[1];P[0]=P[N];
	//Pt fiecare latura a poligonului calculam ec dreptei suport
	for (i=1;i<=N;++i)
	{
		D[i].a=P[i+1].y - P[i].y;
		D[i].b=P[i].x - P[i+1].x;
		D[i].c=P[i+1].x*P[i].y - P[i].x*P[i+1].y;
		if (D[i].b < 0) {D[i].a*=-1;D[i].b*=-1;D[i].c*=-1;}
	}
	//Formam benzile
    nx.reserve(N);
	for (i=1;i<=N;++i) nx.pb(P[i].x);
	sort(nx.begin(),nx.end());
	int nN=unique(nx.begin(),nx.end())-nx.begin()-2;
	//fprintf(stderr,"nN=%d\n",nN);
	nB.reserve(N);
	D[0]=D[N];D[N+1]=D[1];
	for (i=0;i<=nN;++i)
	{
		nB.clear();
		for (j=1;j<=N;++j)
			if (P[j].x == nx[i])
			{
				if (P[j-1].x >= nx[i+1])
                   nB.pb(compute(j-1,nx[i+1],P[j].y));
				if (P[j+1].x >= nx[i+1])
				   nB.pb(compute(j,nx[i+1],P[j].y));
			}
			else
			if (P[j].x == nx[i+1])
			{
				if (P[j-1].x < nx[i])
					nB.pb(compute(j-1,nx[i],P[j].y));
				if (P[j+1].x < nx[i])
					nB.pb(compute(j,nx[i],P[j].y));
			}
		sort(nB.begin(),nB.end());
		for (j=0;j<(int)nB.size();++j) Banda[i].pb(nB[j].second);
	}
	//fprintf(stderr,"%d\n",Banda[0].size());
	//for (i=0;i<Banda[0].size();++i) fprintf(stderr,"%d ",Banda[0][i]);
	//fprintf(stderr,"\n");
	//rezolvam
	for (i=1;i<=M;++i)
	{
		int x,y,l,r,m;
		scanf("%d %d",&x,&y);
		//fprintf(stderr,"%d %d\n",x,y);
		if (x < nx[0] || x > nx[nN+1]) continue;
		for (l=0,r=nN;l<=r;)
		{
			m=(l+r)/2;
			if (nx[m] <= x) j=m,l=m+1;
			else r=m-1;
		}
		//fprintf(stderr,"j=%d\n",j);
		int up=Banda[j].size() -1,ret;
		if (semn(Banda[j][0],x,y) < 0 || semn(Banda[j][up],x,y) > 0) continue;
		for (l=0,r=up;l<=r;)
		{
			m=(l+r)/2;
			if (semn(Banda[j][m],x,y) <=0) ret=m,r=m-1;
			else l=m+1;
		}
		//fprintf(stderr,"ret=%d\n",ret);
		if (semn(Banda[j][ret],x,y) == 0) ret=1;
		sol+=ret&1;
	}
    printf("%d\n",sol);
	return 0;
}