Cod sursa(job #2308973)

Utilizator akaprosAna Kapros akapros Data 28 decembrie 2018 10:07:59
Problema Poligon Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.03 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 p)
{
    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 * b[p] + ci) / bi;

}
bool cmp(const pid &a, const pid &b)
{
    ld y1 = a.second + v[a.first].y, y2 = b.second + v[b.first].y;
    if (fabs(y1 - y2) < e)
        return a.first < b.first;
    return y1 < y2;
}
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]))
        {
            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 = intersPoint(i, j, p);
            else
                Y = (ld)max(v[i].y, v[j].y);

            I[p].push_back(pid{i, Y});
        }
    }
    sort(I[p].begin(), I[p].end(), cmp);
}
int bandBs(int B, Point P)
{
    int i = 0, 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();
    while (p < sz)
        p <<= 1;
    while (p)
    {
        if (i + p < sz && I[id][i + p].second <= e + P.y)
            i += p;
        p >>= 1;
    }
    if (!sz) return false;
    if (fabs(I[id][i].second - P.y) < e)
        return true;
    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;
        getInters(0, n);
        for (int i = 1; i < n; ++ i)
            if (b[i] != b[i - 1])
            {
                b[B] = b[i];
                getInters(B, n);
                ++ B;
            }

        while (m --)
        {
            Point P;
            scanf("%d%d", &P.x, &P.y);
            int band = bandBs(B, P);
            ans += isInside2(n, P, band);
        }
    }
    printf("%d\n", ans);

    return 0;
}