Cod sursa(job #343182)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 25 august 2009 11:24:18
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#include<utility>
#define x first
#define y second
using namespace std;
pair<int,int> a[800],b[60010],p[810],q[810];
int n,m,k,i,j,ff,ss,cnt,px,py,sol;
long long d,det();
void read(),solve();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("poligon.in","r",stdin);
	freopen("poligon.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&ff,&ss);
		a[i].x=ff;
		a[i].y=ss;
	}
}
void solve()
{
	a[n+1].x=a[1].x;a[n+1].y=a[1].y;
	for(i=1;i<=n;i++)
	{
		if(a[i].x<a[i+1].x)
		{
			p[++k].x=a[i].x;
			p[k].y=a[i].y;
			q[k].x=a[i+1].x;
			q[k].y=a[i+1].y;
			continue;
		}
		if(a[i].x>a[i+1].x)
		{
			q[++k].x=a[i].x;
			q[k].y=a[i].y;
			p[k].x=a[i+1].x;
			p[k].y=a[i+1].y;
			continue;
		}
	}
	for(i=1;i<=m;i++)
	{
		cnt=0;scanf("%d%d",&px,&py);
		for(j=1;j<=k;j++)
		{
			if(px<p[j].x)continue;
			if(px>q[j].x)continue;
			d=det();
			if(!d){cnt=1;break;}
			if(d>0)cnt=1-cnt;
		}
		sol+=cnt;
	}
		printf("%d\n",sol);
}
long long det()
{
	long long a1,b1,a2,b2,a3,b3;
	a1=p[j].x;b1=p[j].y;
	a2=q[j].x;b2=q[j].y;
	a3=px;b3=py;
	return a1*b2+a2*b3+a3*b1-b1*a2-b2*a3-b3*a1;
}