Cod sursa(job #425439)

Utilizator loginLogin Iustin Anca login Data 25 martie 2010 18:57:02
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define EPS 0.001
using namespace std;
struct pct{
	double y, x;
	pct(){}
	pct(double I, double J){
		x=I;y=J;}
	};
vector<pct> P, V;
int n, m, rez;

void read()
{
	ifstream fin ("poligon.in");
	fin>>n>>m;
	int x, y;
	for (int i=1;i<=n;i++)
	{
		fin>>x>>y;
		P.push_back(pct(x, y));
	}
	for(int i=1;i<=m;i++)
	{
		fin>>x>>y;
		V.push_back(pct(x, y));
	}
}

int in_p (pct p)
{
	double x;
	int ni=0;
	pct A;
	vector<pct>::iterator I;
//	cout<<p.x<<" "<<p.y;
	for (I=P.begin();I+1<P.end();++I)
	{
		if ((p.y>=I->y && p.y<=(I+1)->y) || (p.y<=I->y && p.y>=(I+1)->y))
		{
			if (I->x==(I+1)->x)
			{
				if (I->x>=p.x)
					++ni;
			}
			else
				if (I->y== (I+1)->y)
				{
					if (I->y==p.y && p.x>=I->x && p.x>=(I+1)->x)
						++ni;
				}
				else
				{
		//			cout<<p.x<<" "<<p.y<<" cu      "<<I->x<<" "<<I->y<<", "<<(I+1)->x<<" "<<(I+1)->y<<" = ";
					x=(p.y-I->y)*((I+1)->x-I->x)/((I+1)->y-I->y)+I->x;
		//			cout<<x<<"  "<<p.y<<endl;
					if (x>=p.x)
						++ni;
				}
		}
	}
		A=*(P.begin());
//		cout<<"capatu "<<I->x<<" "<<I->y<<endl;
		if ((p.y>=I->y && p.y<=A.y) || (p.y<=I->y && p.y>=A.y))
		{
			if (I->x==A.x)
			{
				if (I->x>=p.x)
					++ni;
			}
			else
				if (I->y==A.y)
				{
					if (I->y==p.y && p.x>=I->x && p.x>=A.x)
						++ni;
				}
				else
				{
		//			cout<<p.x<<" "<<p.y<<" cu      "<<I->x<<" "<<I->y<<", "<<(I+1)->x<<" "<<(I+1)->y<<" = ";
					x=(p.y-I->y)*(A.x-I->x)/(A.y-I->y)+I->x;
		//			cout<<x<<"  "<<p.y<<endl;
					if (x>=p.x)
						++ni;
				}
		}
	return ni%2;
}

void solve ()
{
	for(vector<pct>::iterator I=V.begin();I<V.end();++I)
		if (in_p(*I))
			++rez;
}

void afis ()
{
	ofstream fout ("poligon.out");
	fout<<rez<<"\n";
}

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