Cod sursa(job #346671)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 8 septembrie 2009 23:33:28
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 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,nN;
punct P[NMAX];
dreapta D[NMAX];
vector<int> Banda[NMAX],nx;
vector< pair<double,int> > nB;
int semn(int iD,int x,int y)
{
	int ret = D[iD].a*x + D[iD].b*y + D[iD].c;
	if (ret > 0) return 1;
	if (ret == 0) return 0;
	return -1;
}
vector<punct> PS;
int check(int x,int y)
{
	//verificam dc punctul este vf al poligonului
	if (binary_search(PS.begin(),PS.end(),mp(x,y))) return 1;
    if (x < nx[0] || x > nx[nN+1]) return 0;
	int l,r,m,iB=0,nrB=-1;
    for (l=0,r=nN;l<=r;)
	{
		m=(l+r)/2;
		if (nx[m] <= x) iB=m,l=m+1;
		else r=m-1;
	}
	for (l=0,r=Banda[iB].size()-1;l<=r;)
	{
		m=(l+r)/2;
		if (semn(Banda[iB][m],x,y) >= 0) nrB=m,l=m+1;
		else r=m-1;
	}
	if (nrB == -1) return 0;
	if (semn(Banda[iB][nrB],x,y) == 0) return 1;
	return (nrB+1)&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
	PS.reserve(N);
	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;}
		PS.pb(P[i]);
	}
	sort(PS.begin(),PS.end());
	//Formam benzile
    nx.reserve(N);
	for (i=1;i<=N;++i) nx.pb(P[i].x);
	sort(nx.begin(),nx.end());
    nN=unique(nx.begin(),nx.end())-nx.begin()-2;
	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 (min(P[j].x,P[j+1].x) <= nx[i] && max(P[j].x,P[j+1].x) >=nx[i+1])
		  {
			  double a=D[j].a,b=D[j].b,c=2*D[j].c,sx=nx[i]+nx[i+1];
	          nB.pb(mp(-0.5*(a*sx+c)/b , j));
		  }
		sort(nB.begin(),nB.end());
		for (j=0;j<(int)nB.size();++j) Banda[i].pb(nB[j].second);
	}
	//rezolvam
	for (i=1;i<=M;++i)
	{
		int x,y;
		scanf("%d %d",&x,&y);
		sol+=check(x,y);
	}
    printf("%d\n",sol);
	return 0;
}