Cod sursa(job #425308)

Utilizator loginLogin Iustin Anca login Data 25 martie 2010 17:15:58
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 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));
	}
}

pct intersectie (pct p, pct a, pct b)
{
	p.x=(p.y-a.y)*(b.x-a.x)/(b.y-a.x)+a.x;
	return p;
}

int in_p (pct p)
{
	pct A;
	int ni=0;
	for (vector<pct>::iterator I=P.begin();I+1<P.end();++I)
		if ((p.x>=I->x && p.x<=(I+1)->x) || (p.x<=I->x && p.x>=(I+1)->x))
		{
			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
				{
					A=intersectie(p, *I, *(I+1));
					cout<<A.x<<"  "<<A.y<<endl;
					if (A.x>=p.x+EPS)
						++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;
}