Cod sursa(job #2593376)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 3 aprilie 2020 18:41:49
Problema Poligon Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.36 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;
    }
 
	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(double x) const
	{
	    if (b == 0)
            return -Infd;
 
	    return 1.*(-c - a * x) / b;
	}
 
	void Write()
	{
	    cout << "Dreapta intre punctele " << p1.x << ' ' << p1.y << "; " << p2.x << ' ' << p2.y << "; ";
	    cout << " cu ecuatia " << a << "*x + " << b << "*y + " << c << " = 0\n";
	}
};
 
struct Compare{
    static int x1, x2;
 
    static bool Cmp(const Segment& s1, const Segment& s2)
    {
        return s1.GetY(1.*(x1 + x2) / 2) < s2.GetY(1.*(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 && sgm[lo].b == 0)
        {
            if (Abs((1. * -sgm[lo].c) / sgm[lo].a - p.x) < eps
                && min(sgm[lo].p1.y, sgm[lo].p2.y) <= p.y && p.y <= max(sgm[lo].p1.y, sgm[lo].p2.y))
                    return true;
            ++lo;
        }
 
        while (lo <= hi)
        {
            mid = (lo + hi) / 2;
 
            if (sgm[mid].GetY(p.x) >= p.y)
                res = mid, hi = mid - 1;
            else
                lo = mid + 1;
        }
 
    /*    cout << (static_cast<int>(sgm.size()) - res) << '\n';
        for (size_t i = res; i < sgm.size(); ++i)
            sgm[i].Write();     */
 
        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';
	//cout << cnt;
 
	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 (p.x == xmin || p.x == xmax)
    {
        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);
}