Cod sursa(job #1724106)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 2 iulie 2016 12:49:42
Problema Poligon Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("poligon.in");
ofstream g("poligon.out");
const int NMax = 805;
const int PMax = 60005;
const double eps = 0.000001;
int N, M, ans;
pair <int, int> Point[NMax];
bool Abs[PMax];
vector <int> V;
int Poz[PMax], Poz2[PMax];
vector <pair< pair<double, double>, pair <double, double> > > Band[PMax];
void Read()
{
    f >> N >> M;
    for(int i = 1; i <= N; i++)
        f >> Point[i].first >> Point[i].second, Abs[Point[i].first] = 1;
}

void buildV()
{
    int last = 0;
    for(int i = 0; i <= PMax - 5; i++)
    {
        Poz2[i] = last;
        if(Abs[i] == 1)
            V.push_back(i), Poz[i] = V.size() - 1, last = V.size() - 1;
    }

}
inline void findCoefficients(pair<double, double> p1, pair<double, double> p2, double& A, double& B, double& C)
{
    A=p2.second-p1.second;
    B=p1.first-p2.first;
    C=p2.first*p1.second-p2.second*p1.first;
}
inline double findIntersection(double A, double B, double C, double abs)
{
    return (-C - A * abs) / B;
}
void buildBand()
{
    Point[N + 1] = Point[1];
    for(int i = 1; i <= N; i++)
    {
        double A, B, C;
        findCoefficients(Point[i], Point[i + 1], A, B, C);
        int x = Poz[Point[i].first], y = Poz[Point[i + 1].first];
        if(x > y)
            swap(x, y);
        for(int j = x; j < y; j++)
        {
            Band[j].push_back(make_pair(make_pair(V[j], findIntersection(A, B, C, V[j])), make_pair(V[j + 1], findIntersection(A, B, C, V[j + 1]))));
        }
    }
}
inline bool cmp(pair < pair<double, double>, pair <double, double> > a, pair <pair <double, double>, pair <double, double> >b)
{
    return a.first.second + a.second.second  > b.first.second + b.second.second;
}
void sortBand()
{
    for(int i = 0 ;i < V.size() - 1; i++)
        sort(Band[i].begin(), Band[i].end(), cmp);
}
inline double area(pair <double, double> a, pair <double, double> b, pair <double, double> c)
{
    return a.first * b.second + b.first * c.second + c.first * a.second - a.second * b.first - b.second * c.first - c.second * a.first;
}
int findBand(pair <double, double> p)
{
    if(p.first < V[0] || p.first > V[V.size() - 1])
        return -1;
    int sol = 0;
    /*int left = 0, right = V.size() - 1, mid, sol = 0;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(V[mid] < p.first)
        {
            sol = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }*/
    sol = Poz2[(int)p.first];
    if(sol == V.size() - 1)
        return -1;
    return sol;
}
void binarySearch(pair <double, double> p)
{
    int poz = findBand(p);
    if(poz == -1)
        return;
    int s = (1 << 9);
    int left = 0, right = Band[poz].size() - 1, mid, sol = -1;
    while(s > 0)
    {
        if(sol + s >= Band[poz].size())
        {
            s /= 2;
            continue;
        }
        double x = area(Band[poz][sol + s].first, Band[poz][sol + s].second, p);
        if(x >= - eps && x <= eps)
        {
            ans++;
            return;
        }
        if(x < -eps)
        {
            sol += s;
        }
        s /= 2;
    }
    if((sol + 1) % 2 == 1)
        ans++;
}
int main()
{
    Read();
    buildV();
    buildBand();
    sortBand();
    for(int i = 1; i <= M; i++)
    {
        pair <int, int> p;
        f >> p.first >> p.second;
        binarySearch(p);
    }
    g << ans << "\n";
    return 0;
}