Cod sursa(job #2308991)

Utilizator akaprosAna Kapros akapros Data 28 decembrie 2018 11:22:20
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.26 kb
#include <bits/stdc++.h>
#define maxN 802
#define INF 0x3fffffff
#define ll long long
#define ld long double
#define pid pair <int, double>
#define e 1e-9

using namespace std;

FILE *fin = freopen("poligon.in", "r", stdin);
FILE *fout = freopen("poligon.out", "w", stdout);

struct Point
{
    int x, y;
    bool operator != (const Point &p) const
    {
        return (x != p.x || y != p.y);
    }
} v[maxN];

int b[maxN];
vector < pid > I[maxN];

/// Given three colinear points p, q, r, the function checks if
/// point q lies on line segment 'pr'
bool onSegment(Point p, Point q, Point r)
{
    return (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
            q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y));
}
/// To find orientation of ordered triplet (p, q, r).
int orientation(Point p, Point q, Point r)
{
    ll det = 1LL * (q.y - p.y) * (r.x - q.x) - 1LL * (q.x - p.x) * (r.y - q.y);
    if (det == 0) return 0;  // colinear
    return (det > 0)? 1: 2; // clock or counterclock wise
}
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
    /// Find the four orientations needed for general and
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    /// General case
    if (o1 != o2 && o3 != o4)
        return true;
    /// Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
    // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
    return false; /// Doesn't fall in any of the above cases
}
bool isInside1(Point p, int n)
{
    Point extreme = {INF, p.y};
    int cnt = 0;
    for (int i = 0; i < n; ++ i)
    {
        int j = (i + 1) % n;
        if (doIntersect(v[i], v[j], p, extreme))
        {
            if (orientation(v[i], p, v[j]) == 0)
                return onSegment(v[i], p, v[j]);
            if ((v[i].y > v[j].y && onSegment(p, v[i], extreme)) ||
                    (v[i].y <= v[j].y && onSegment(p, v[j], extreme)))
                ++ cnt;
            if (!onSegment(p, v[i], extreme) && !onSegment(p, v[j], extreme))
                ++ cnt;
        }
    }
    return (cnt & 1);
}
///* --------------------------  O(N^2logN + MlogN) -------------------------- */
ld intersPoint(int i, int j, int X)
{
    ld ai = -(v[j].y - v[i].y),
       bi = (v[j].x - v[i].x),
       ci = (ld)v[i].x * v[j].y - (ld)v[i].y * v[j].x;
    return -(ai * X + ci) / bi;

}
bool cmp(const pid &a, const pid &b)
{
    if (fabs(a.second - b.second) < e)
        return a.first < b.first;
    return a.second > b.second;
}
void getInters(int p, int n)
{
    Point A = {b[p], -INF}, B = {b[p], INF};
    for (int i = 0; i < n; ++ i)
    {
        int j = (i + 1) % n;
        if (doIntersect(A, B, v[i], v[j]) && max(v[i].x, v[j].x) > b[p])
        {
            //if (onSegment(A, v[i], B) && v[i].y < v[j].y) continue;
            //if (onSegment(A, v[j], B) && v[j].y < v[i].y) continue;
            ld Y;
            //if (v[i].x != v[j].x)
            Y = (0.5 * (v[j].y - v[i].y) * (b[p] + b[p + 1]) + (ld)v[j].x * v[i].y - (ld)v[i].x * v[j].y) / (v[j].x - v[i].x);

            I[p].push_back(pid{i, Y});
        }
    }
    sort(I[p].begin(), I[p].end(), cmp);
}
int bandBs(int B, Point P)
{
    int i = -1, p = 1;
    while (p < B)
        p <<= 1;
    while (p)
    {
        if (i + p < B && b[i + p] < P.x)
            i += p;
        p >>= 1;
    }
    return i;
}
bool isInside2(int n, Point P, int id)
{
    int i = -1, p = 1, sz = I[id].size();

    if (!sz) return false;
    while (p < sz)
        p <<= 1;
    while (p)
    {
        if (i + p < sz)
        {
            int p1 = I[id][i + p].first, p2 = (I[id][i + p].first + 1) % n;
            if (intersPoint(p1, p2, P.x) + e >= P.y)
            {
                i += p;
                if (onSegment(v[p1], P, v[p2]))
                    return true;
            }
        }
        p >>= 1;
    }

    return ((i + 1) & 1);
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++ i)
    {
        scanf("%d%d", &v[i].x, &v[i].y);
        b[i] = v[i].x;
    }

    int ans = 0;
    if (m <= 0)
    {
        while (m --)
        {
            Point P;
            scanf("%d%d", &P.x, &P.y);
            ans += isInside1(P, n);
        }
    }
    else
    {
        sort(b, b + n);
        int B = 1;
        for (int i = 1; i < n; ++ i)
            if (b[i] != b[i - 1])
                b[B ++] = b[i];
        b[B] = 0;
        for (int i = 0; i < B; ++ i)
            getInters(i, n);

        while (m --)
        {
            Point P;
            scanf("%d%d", &P.x, &P.y);
            if (P.x < b[0] || P.x > b[B - 1])
                continue;
            int band = bandBs(B, P);
            ans += isInside2(n, P, band);
        }
    }
    printf("%d\n", ans);

    return 0;
}