Cod sursa(job #2641848)

Utilizator Alin_StanciuStanciu Alin Alin_Stanciu Data 12 august 2020 21:48:35
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#define MAX_N 800
#define MAX_M 60000

//#include <iostream>

#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("poligon.in");
ofstream fout("poligon.out");

struct point
{
	int x, y;
};

int n, m;
point P[MAX_N + 1], C[MAX_M + 1];
point corner = { 60001, 60001 };

int Sign(const point& p1, const point& p2, const point& p3);

bool IsInside(const point& p);

//void CoutPoint(const point& p);

int main()
{
	fin >> n >> m;
	
	for (int i = 1; i <= n; ++i)
	{
		fin >> P[i].x >> P[i].y;
		
		if (corner.x > P[i].x)
		{
			corner = P[i];
		}
		else
		{
			if (corner.x == P[i].x)
			{
				if (corner.y > P[i].y)
				{
					corner = P[i];
				}
			}
		}
	}
	
	int r = 0;
	for (int i = 1; i <= m; ++i)
	{
		fin >> C[i].x >> C[i].y;
		
		bool inside = IsInside(C[i]);
		
		if (inside)
		{
			++r;
		}
		
		/*
		cout << "Is inside: " << inside << "; " << "{ " << C[i].x << ", " << C[i].y << " }\n";
		cin.get();
		*/
	}
	
	fout << r;
	
	fin.close();
	fout.close();
	return 0;
}

/*
void CoutPoint(const point& p)
{
	cout << "{ " << p.x << ", " << p.y << " }";
}
*/

int Sign(const point& p1, const point& p2, const point& p3)
{
	return ((p1.x - p3.x) * (p2.y - p3.y)) - ((p2.x - p3.x) * (p1.y - p3.y));
}

bool IsInside(const point& p)
{
	int intersectionCount = 0;
	
	for (int i = 1; i <= n; ++i)
	{
		point p1, p2;
		
		if (i < n)
		{
			p1 = P[i];
			p2 = P[i + 1];
		}
		else
		{
			p1 = P[n];
			p2 = P[1];
		}
		
		const int sngp1 = Sign(corner, p, p1);
		const int sngp2 = Sign(corner, p, p2);
		
		const bool psngp1 = sngp1 >= 0;
		const bool psngp2 = sngp2 >= 0;
		
		if ((sngp1 == 0) && (sngp2 == 0))
		{
			//cout << "sngp1 = sngp2 = 0\n";
			
			if ((p1.x == 0) && (p2.x == 0))
			{
				if ((min(p1.y, p2.y) <= p.y) && (p.y <= max(p1.y, p2.y)))
				{
					/*
					cout << "x1 = x2 = 0;\n";
					CoutPoint(corner);
					cout << ' ';
					CoutPoint(p);
					cout << ' ';
					CoutPoint(p1);
					cout << ' ';
					CoutPoint(p2);
					cout << '\n';
					cin.get();
					*/
					
					return true;
				}
			}
			else
			{
				if ((min(p1.x, p2.x) <= p.x) && (p.x <= max(p1.x, p2.x)))
				{
					/*
					CoutPoint(corner);
					cout << ' ';
					CoutPoint(p);
					cout << ' ';
					CoutPoint(p1);
					cout << ' ';
					CoutPoint(p2);
					cout << '\n';
					cin.get();
					*/
					
					return true;
				}
			}
		}
		
		if (psngp1 == psngp2)
		{
			continue;
		}
		
		point a1 = p1;
		point a2 = p2;
		
		if (sngp2 < 0)
		{
			swap(a1, a2);
		}
		
		if (Sign(a1, a2, p) >= 0)
		{
			++intersectionCount;
		}
	}
	
	/*
	cout << "Intersection count: " << intersectionCount << "; " << "{ " << p.x << ", " << p.y << " }\n";
	cin.get();
	*/
	
	return intersectionCount & 1;
}