Cod sursa(job #711576)

Utilizator fhandreiAndrei Hareza fhandrei Data 12 martie 2012 13:20:20
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.29 kb
//Include
#include <fstream>
//#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
using namespace std;

//Definitii
#define pentruTrimis
#define x first
#define y second
#define tipPuncte int

//Constante
const tipPuncte oo = (tipPuncte)2e9;

//Functii
inline tipPuncte determinant(pair<tipPuncte, tipPuncte> a, pair<tipPuncte, tipPuncte> b, pair<tipPuncte, tipPuncte> c);
inline bool apartine(pair<tipPuncte, tipPuncte> left, pair<tipPuncte, tipPuncte> right, pair<tipPuncte, tipPuncte> what);
inline int dist(pair<tipPuncte, tipPuncte> left, pair<tipPuncte, tipPuncte> right);
inline bool seIntersecteaza(pair<tipPuncte, tipPuncte> left1, pair<tipPuncte, tipPuncte> right1, pair<tipPuncte, tipPuncte> left2, pair<tipPuncte, tipPuncte> right2);

//Variabile
ifstream in("poligon.in");
ofstream out("poligon.out");
	
int n, m;
int intersectii;
int rasp;

bool pePoligon;

tipPuncte detI;

pair<tipPuncte, tipPuncte> cautat, exterior = make_pair(oo, oo);
vector<pair<tipPuncte, tipPuncte> > puncte;

//Main
int main()
{
#ifdef pentruTrimis
	in >> n >> m;
#else
	in >> n;
#endif
	puncte.resize(n+2);
	for(int i=1 ; i<=n ; ++i)
	{
		in >> puncte[i].x >> puncte[i].y;
		if(puncte[i] < exterior)
			exterior = puncte[i];
	}
	
	--exterior.x;
	--exterior.y;
	
	puncte[0]=puncte[n];
	puncte[n+1]=puncte[1];
#ifdef pentruTrimis	
	for(int k=1 ; k<=m ; ++k)
	{
#endif
		in >> cautat.x >> cautat.y;
		pePoligon = false;
		intersectii = 0;
		for(int i=1 ; i <=n ; ++i)
		{
			if(!determinant(cautat, puncte[i], puncte[i+1]))
			{
				if(apartine(puncte[i], puncte[i+1], cautat))
				{
					pePoligon = true;
					break;
				}
			}
			
			
			detI = determinant(exterior, cautat, puncte[i]);
			if(!detI)
			{
				if((determinant(exterior, cautat, puncte[i-1]) * determinant(exterior, cautat, puncte[i+1]) < 0) && apartine(exterior, cautat, puncte[i]))
					++intersectii;
			}
			else if(determinant(exterior, cautat, puncte[i-1]) * detI < 0)
				if(seIntersecteaza(exterior, cautat, puncte[i], puncte[i-1]))
					++intersectii;
		}
#ifndef pentruTrimis
		if(pePoligon)
			out << "Punctul se afla pe poligon";
		else if(intersectii & 1)
			out << "Punctul se afla in interiorul poligonului";
		else out << "Punctul se afla in exteriorul poligonului";
#else		
		if(pePoligon || (intersectii & 1))
			++rasp;
	}
	
	out << rasp;
#endif

	in.close();
	out.close();
	return 0;
}

inline tipPuncte determinant(pair<tipPuncte, tipPuncte> a, pair<tipPuncte, tipPuncte> b, pair<tipPuncte, tipPuncte> c)
{	return (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x);	}

inline bool apartine(pair<tipPuncte, tipPuncte> left, pair<tipPuncte, tipPuncte> right, pair<tipPuncte, tipPuncte> what)
{	return (dist(left, what) + dist(right, what) == dist(left, right));	}

inline int dist(pair<tipPuncte, tipPuncte> left, pair<tipPuncte, tipPuncte> right)
{
	double radical = sqrt( (right.x - left.x)*(right.x - left.x) + (right.y - left.y)*(right.y - left.y) );
	return (int) round(radical*1e3);
}

inline bool seIntersecteaza(pair<tipPuncte, tipPuncte> left1, pair<tipPuncte, tipPuncte> right1, pair<tipPuncte, tipPuncte> left2, pair<tipPuncte, tipPuncte> right2)
{
	return	(determinant(left1, right1, left2) * determinant(left1, right1, right2) < 0 &&
			determinant(left2, right2, left1) * determinant(left2, right2, right1) < 0);
	
	
}