Cod sursa(job #1906207)

Utilizator popabogdanPopa Bogdan Ioan popabogdan Data 6 martie 2017 12:46:12
Problema Poligon Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.01 kb
#include <bits/stdc++.h>
#define nmax 802
#define Cmax 60004
#define eps 1e-8
#define ll long long
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct point
{
   int x;
   long double y;
};
struct segment
{
    point A, B;
};
struct stripe
{
    int x1, x2;
    vector <segment> Segments;
};
vector <stripe> Stripes;
point P[nmax];
vector <point>V[Cmax];
int X[nmax];
int n, M;
int lg;
int i, j;
int x, y;
int sol;
void displayPoint(point A)
{
    cout << A.x << " " << A.y << " ";
}
bool equals(long double a, long double b)
{
    return (abs(a - b) < eps);
}
bool qxSegment(segment a, segment b)
{
    return min(a.A.y, a.B.y) < min(b.A.y, b.B.y) || (equals(min(a.A.y, a.B.y), min(b.A.y, b.B.y)) && max(a.A.y, a.B.y) < max(b.A.y, b.B.y));
}
bool intersect(int x1, int x2, int x3, int x4)
{
    return max(x1, x3) < min(x2, x4);
}
bool qxPoint(point a, point b)
{
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
long double getYCoordinate(point A, point B, long double X)
{
    return (long double)(X - A.x) * (B.y - A.y) / (B.x - A.x) + A.y;
}
void preprocess()
{
    int i, j;
    sort(X + 1, X + n + 1);
    int lg = 1;
    for(i = 2; i <= n; i++)
        if(X[i] != X[lg])
        X[++lg] = X[i];
    stripe S;
    for(i = 1; i < lg; i++)
    {
        S.x1 = X[i];
        S.x2 = X[i + 1];
        for(j = 1; j < n; j++)
            if(intersect(X[i], X[i + 1], min(P[j].x , P[j + 1].x), max(P[j].x , P[j + 1].x)) && P[j].x != P[j + 1].x)
            {
                if(P[j].x < P[j + 1].x)
                    S.Segments.push_back({{X[i], getYCoordinate(P[j], P[j + 1], X[i])}, {X[i + 1], getYCoordinate(P[j], P[j + 1], X[i + 1])}});
                else S.Segments.push_back({{X[i], getYCoordinate(P[j + 1], P[j], X[i])}, {X[i + 1], getYCoordinate(P[j + 1], P[j], X[i + 1])}});
            }
            if(intersect(X[i], X[i + 1], min(P[1].x , P[n].x), max(P[1].x , P[n].x)) && P[1].x != P[n].x)
            {
                if(P[1].x < P[n].x)
                    S.Segments.push_back({{X[i], getYCoordinate(P[1], P[n], X[i])}, {X[i + 1], getYCoordinate(P[1], P[n], X[i + 1])}});
                else S.Segments.push_back({{X[i], getYCoordinate(P[n], P[1], X[i])}, {X[i + 1], getYCoordinate(P[n], P[1], X[i + 1])}});
            }
        sort(S.Segments.begin(), S.Segments.end(), qxSegment);
        Stripes.push_back(S);
     //   for(j = 0; j < S.Segments.size(); j++)
      //      displayPoint(S.Segments[j].A), displayPoint(S.Segments[j].B), cout << "\n";
     //   cout << "\n\n\n";
        S.Segments.clear();
    }
    for(i = 1; i < n; i++)
        if(P[i].x == P[i + 1].x)
         V[P[i].x].push_back({min(P[i].y, P[i + 1].y), max(P[i].y, P[i + 1].y)});
    if(P[1].x == P[n].x)
         V[P[1].x].push_back({min(P[1].y, P[n].y), max(P[1].y, P[n].y)});
}

int getStripePosition(point A)
{
    int s = 0, d = Stripes.size() - 1, m;
    while(s <= d)
    {
        m = (s + d) / 2;
        if(Stripes[m].x1 <= A.x && Stripes[m].x2 >= A.x)
            return m;
        if(Stripes[m].x1 > A.x)
            d = m - 1;
        else s = m + 1;
    }
    return - 1;

}
long double side(point A, segment S)
{
    return (long double)(A.y - S.A.y) * (S.B.x - S.A.x) - (long double)(A.x - S.A.x) * (S.B.y - S.A.y);
}
bool onSegment(point A, segment S)
{
    return side(A, S) == 0 && (A.x >= S.A.x && A.x <= S.B.x) && (A.y >= min(S.A.y, S.B.y) && A.y <= max(S.A.y, S.B.y));
}
int inside(point A)
{
    int pos = getStripePosition(A);
    if(pos == - 1)
        return 0;
    int s = 0, d = V[A.x].size() - 1, m, best = -1;
    for(s = 0; s <= d; s++)
        if(V[A.x][s].x <= A.y && A.y <= V[A.x][s].y)
        return 1;
   // for(i = 0; i < Stripes[pos].Segments.size(); i++)
   //     displayPoint(Stripes[pos].Segments[i].A), displayPoint(Stripes[pos].Segments[i].B), cout << "\n";
    s = 0, d = Stripes[pos].Segments.size() - 1, m, best = -1;
    while(s <= d)
    {
        m = (s + d) / 2;
        if(side(A, Stripes[pos].Segments[m]) >= 0)
        {
            best = m;
            s = m + 1;
        }
        else d = m - 1;
    }
    return (best + 1) % 2 || onSegment(A, Stripes[pos].Segments[best]);
}
set < pair <int , int> >Set;
int main()
{
    fin >> n >> M;
    for(i = 1; i <= n; i++)
    {
        fin >> P[i].x >> P[i].y;

      // P[i].x += 1003;
       //P[i].y += 1003;
        Set.insert(make_pair(P[i].x, P[i].y));
        X[i] = P[i].x;
        //cout << P[i].x << " " << P[i].y << "\n";
    }
    preprocess();
  //  cout << getYCoordinate({5, 4}, {11, 9}, 8) << "\n";

    while(M--)
    {

        fin >> x >> y;
    //    x += 1003;
    //y += 1003;
       if(Set.find(make_pair(x, y)) != Set.end())
        sol++;
     else
            sol += inside({x, y});
 //cout << x << " " << y << "\n";
   // if(Set.find(make_pair(x, y)) != Set.end() || inside({x, y}))
   //       fout << "DA\n";
    //  else fout << "NU\n";
    }
    fout << sol << "\n";
    return 0;
}