Cod sursa(job #2444169)

Utilizator borcanirobertBorcani Robert borcanirobert Data 30 iulie 2019 14:35:20
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.55 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;
const int Inf = 0x3f3f3f3f;
const double Infd = 1e10;
double Abs(double a)
{
	return a >= 0 ? a : -a;
}

struct Point{
	int x, y;

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

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

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

int xmin{Inf}, xmax{-Inf};

struct Segment{
	Point p1, p2;
	int 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;
	}

	double GetY(int x) const
	{
	    if (b == 0)
            return -Infd;

	    return 1.*(-c - a * x) / b;
	}
};

struct Compare{
    static int x1, x2;

    static bool Cmp(const Segment& s1, const Segment& s2)
    {
        return s1.GetY((x1 + x2) / 2) < s2.GetY((x1 + x2) / 2);
    }
};
int Compare::x1 = 0;
int Compare::x2 = 0;

struct Strip{
    int x1, x2;
    vector<Segment> sgm;

    Strip(int x1, int x2, const vector<Segment>& potentialSegm)
            : x1{x1}, x2{x2}
    {
        for (const Segment& s : potentialSegm)
        {
            if (min(s.p1.x, s.p2.x) <= x2 && max(s.p1.x, s.p2.x) >= x1 && s.b != 0)
                sgm.push_back(s);
        }

        Compare::x1 = x1;
        Compare::x2 = x2;
        sort(sgm.begin(), sgm.end(), Compare::Cmp);
    }

    bool Intersect(Point p)
    {
        int lo{0}, hi{static_cast<int>(sgm.size()) - 1}, mid, res{static_cast<int>(sgm.size())};
        while (lo <= hi)
        {
            mid = (lo + hi) / 2;

            if (sgm[mid].GetY(p.x) >= p.y)
                res = mid, hi = mid - 1;
            else
                lo = mid + 1;
        }

        return ((static_cast<int>(sgm.size()) - res) & 1);
    }

    void Write()
    {
        cout << "Segmentul " << x1 << " - " << x2 << " : ";
        for (const Segment& s : sgm)
            cout << "( " << s.p1.x << ' ' << s.p1.y << "; " << s.p2.x << ' ' << s.p2.y << " );";
        cout << '\n';
    }
};

int N, M;
vector<Point> p;
vector<Segment> s;
vector<Strip> st;
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;
		xmin = min(xmin, p[i].x);
		xmax = max(xmax, p[i].x);
    }
}

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

    sort(p.begin(), p.end());
    vector<int> X;
    for (const Point& P : p)
        if (X.empty() || X.back() != P.x)
            X.push_back(P.x);

    for (size_t i = 0; i + 1 < X.size(); ++i)
    {
        st.emplace_back(X[i], X[i + 1], s);
    //    st.back().Write();
    }
}

bool Check(Point p)
{
    if (p.x < xmin || p.x > xmax)
        return false;
   // if (find(::p.begin(), ::p.end(), p) != ::p.end())
   //     return true;

    int lo{0}, hi{static_cast<int>(st.size()) - 1}, mid, res;
    while (lo <= hi)
    {
        mid = (lo + hi) / 2;

        if (st[mid].x1 <= p.x)
            res = mid, lo = mid + 1;
        else
            hi = mid - 1;
    }

    return st[res].Intersect(p);
}