Cod sursa(job #262530)

Utilizator blasterzMircea Dima blasterz Data 19 februarie 2009 14:05:43
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
using namespace std;
#include <algorithm>
#include <vector>
#include <cstdio>
#include <string>
#define dim 8192
char ax[dim];
int pz=0;

inline void cit(int &x)
{
	x=0;
	while(ax[pz] < '0' || ax[pz] > '9')
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	while(ax[pz] >= '0' && ax[pz] <= '9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
	}
}

struct nod { int x, y; nod(){}; nod(int _x, int _y){x=_x; y=_y;};};

struct edge{ nod x, y; double my;edge(){}; edge(nod a, nod b){x=a; y=b; my=(a.y+b.y)/2.0;};};


struct cmp{
	bool operator()(const nod &a, const nod &b)const
	{
		if(a.x < b.x) return 1;
		if(a.x == b.x) if(a.y < b.y) return 1;
		return 0;
	}
};

struct cmp1{
	bool operator()(const edge &a, const edge &b)const
	{
		if(a.my < b.my) return 1;
		return 0;
	}
};


nod a[801];
nod fasii[801];
vector<edge> seg_fasii[801];

int n, m;



void read()
{
	freopen("poligon.in","r",stdin);
	cit(n);cit(m);
	
	for(int i=1; i <= n; ++i) cit(a[i].x), cit(a[i].y);
	a[n+1]=a[1];
}

inline int intersecteaza(int x1, int x2, nod x, nod y)
{
	if(x.x < x1 && y.x < x1) return 0;
	if(x.x > x2 && y.x > x2) return 0;
	return 1;
}

inline int isleft(nod p0, nod p1, nod p2)
{
	int t=(p1.x-p0.x)*(p2.y-p0.y) - (p2.x-p0.x)*(p1.y-p0.y);
	
	if(t > 0) return 1;
	if(t < 0) return -1;
	return 0;
}


void afis(edge a)
{
	printf("%d %d %d %d\n", a.x.x, a.x.y, a.y.x, a.y.y);
}



void solve()
{
	int i, j;
	
	for(i=1; i <= n; ++i) fasii[i]=a[i];
	
	sort(fasii+1, fasii+n+1, cmp());
	// o fasie e intre fasii[i] si fasii[i+1]
	
	for(i=1; i < n; ++i)
	{
		for(j=1; j <= n; ++j)
			if( intersecteaza(fasii[i].x, fasii[i+1].x, a[j], a[j+1]) )
				seg_fasii[i].push_back(edge(a[j], a[j+1]));
	
			sort(seg_fasii[i].begin(), seg_fasii[i].end(), cmp1());
	
	}
	
	
	for(i=1; i < n; ++i)
	{
		for(j=0; j < seg_fasii[i].size(); ++j)
		{
			edge t=seg_fasii[i][j];
			
			if(t.x.x > t.y.x)
			{
				nod aux=t.x;
				t.x=t.y;
				t.y=aux;
			}
		}
	}
	
	
	
}

void doit()
{
	int i, j, cnt;
	nod p;
	int sol=0;
	while(m--)
	{
		cit(p.x);cit(p.y);
		
		for(i=1, cnt=(1<<20); cnt; cnt>>=1)
			if(i + cnt < n)
				if(p.x >= fasii[i+cnt].x) i+=cnt;
			
		
		for(j=0, cnt=(1<<10); cnt; cnt>>=1)
			if(j + cnt < seg_fasii[i].size())
				if(isleft(p, seg_fasii[i][j+cnt].x, seg_fasii[i][j+cnt].y) >= 0)
					j+=cnt;
				
				
		//printf("sol: %d\n", j);
		//printf("%d %d__", p.x, p.y);
		//afis(seg_fasii[i][j]);
		
		//printf("isleft %d\n", isleft(p, seg_fasii[i][j].x, seg_fasii[i][j].y));
		if((j+1)&1) ++sol;
	}
	
	freopen("poligon.out","w",stdout);
	printf("%d\n",sol);
	
}

int main()
{
	read();
	solve();
	doit();
	
	return 0;
}