Cod sursa(job #2444087)

Utilizator borcanirobertBorcani Robert borcanirobert Data 30 iulie 2019 12:28:01
Problema Poligon Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

const double eps = 0.0000001;
double Abs(double a)
{
	return a >= 0 ? a : -a;
}

struct Point{
	double x, y;

	bool operator == (const Point& p) const
	{
	    return Abs(p.x - x) < eps && Abs(p.y - y) < eps;
	}
};

struct Line{
	double a, b, c;
};

struct Segment{
	Point p1, p2;
	double a, b, c;

	Segment(Point p1, Point p2)
        : p1(p1), p2(p2)
	{
		a = p1.y - p2.y;
		b = p2.x - p1.x;
		c = p1.x * p2.y - p2.x * p1.y;
	}

	int Intersect(Point p) const		// 0 - nu intersecteaza, 1 - intersecteaza segmentul, 2 - se afla pe segment
	{
		Line other{1, 0, -p.x};

		if (Abs(a * p.x + b * p.y + c) < eps)
		{
			if (min(p1.x, p2.x) <= p.x && p.x <= max(p1.x, p2.x)
					&& min(p1.y, p2.y) <= p.y && p.y <= max(p1.y, p2.y))
                return 2;
		}

		if (Abs(other.b * a - b * other.a) < eps)
			return 0;

		Point I{(b * other.c - other.b * c) / (other.b * a - b * other.a)
				,(other.a * c - a * other.c)  / (other.b * a - b * other.a)};

        if (I == p1)
            return 0;

        bool ok = (min(p1.x, p2.x) <= I.x && I.x <= max(p1.x, p2.x)
					&& min(p1.y, p2.y) <= I.y && I.y <= max(p1.y, p2.y) && I.y >= p.y);

     //   cout << p1.x << ' ' << p1.y << "; " << p2.x << ' ' << p2.y << "   " << I.x << ' ' << I.y << "  -> " << ok << '\n';

		return ok;
	}
};

int N, M;
vector<Point> p;
vector<Segment> s;
int cnt;

void ReadData();
void MakeSegments();
bool Check(Point p);

int main()
{
	ReadData();
	MakeSegments();

	Point p;
	for (int i = 1; i <= M; ++i)
	{
		fin >> p.x >> p.y;
		cnt += Check(p);
	}

	fout << cnt << '\n';

	fin.close();
	fout.close();
	return 0;
}

void ReadData()
{
	fin >> N >> M;

	p = vector<Point>(N);

	for (int i = 0; i < N; ++i)
		fin >> p[i].x >> p[i].y;
}

void MakeSegments()
{
	for (int i = 0; i < N; ++i)
		s.emplace_back(p[i], p[(i + 1) % N]);
}

bool Check(Point p)
{
	int cnt{0}, r;
	for (const Segment& segm : s)
	{
		r = segm.Intersect(p);

	//	cout << r << '\n';

		if (r == 2)
			return true;
		cnt += r;
	}

	//cout << cnt << "\n\n\n";

	return (cnt & 1);
}