Cod sursa(job #2410034)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 19 aprilie 2019 17:39:39
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <vector>
using namespace std;

#define FILE_NAME "poligon"
ifstream in (FILE_NAME".in");
ofstream out(FILE_NAME".out");
typedef long long LL;
struct punct
{
    LL x, y;
    punct(LL _x = 0, LL _y = 0)
    {
        x = _x;
        y = _y;
    }
};
struct segment
{
    punct A, B;
    segment(punct _A = punct(0, 0), punct _B = punct(0, 0))
    {
        A = _A;
        B = _B;
    }
};
vector < segment > Edges;
int N, M;

LL det(punct A, punct B, punct C)
{
    return (A.x * B.y + B.x * C.y + C.x * A.y) -
           (A.y * B.x + B.y * C.x + C.y * A.x);
}

bool cross(segment POI, segment edge)
{
    LL p = det(POI.A, POI.B, edge.A);
    LL q = det(POI.A, POI.B, edge.B);
    LL s = det(edge.A, edge.B, POI.A);
    LL t = det(edge.A, edge.B, POI.B);
    if(p * q < 0 &&
       s * t < 0)
        return true;
    return false;
}

bool onEdge(punct crima, segment edge)
{
    LL left, right, down, up;
    left = min(edge.A.x, edge.B.x);
    right = left ^ edge.A.x ^ edge.B.x;
    down = min(edge.A.y, edge.B.y);
    up = down ^ edge.A.y ^ edge.B.y;

    if(left <= crima.x && crima.x <= right &&
       down <= crima.y && crima.y <= up &&
       det(crima, edge.A, edge.B) == 0)
        return true;
    return false;
}

int main()
{
    in >> N >> M;
    Edges.reserve(N+4);

    LL prevA, prevB;
    in >> prevA >> prevB;
    LL remA = prevA, remB = prevB;
    for(int i = 2; i <= N; ++i)
    {
        LL A, B;
        in >> A >> B;
        Edges.push_back(segment(punct(prevA, prevB), punct(A, B)));
        prevA = A, prevB = B;
    }
    Edges.push_back(segment(punct(prevA, prevB), punct(remA, remB)));

    int Result = 0;
    while(M--)
    {
        LL x, y;
        in >> x >> y;

        punct crima = punct(x, y);
        segment POI = segment(crima, punct(x+1, 666013));

        int crossCount = 0;
        for(auto edge : Edges)
        {
            if(onEdge(crima, edge))
            {
                crossCount = 1;
                break;
            }
            else if(cross(POI, edge))
                ++crossCount;
        }

        if(crossCount&1)
            ++Result;
    }

    out << Result << '\n';

    return 0;
}