Cod sursa(job #2514094)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 24 decembrie 2019 15:01:33
Problema Poligon Scor 100
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 2.66 kb
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define dbg(x) cerr << #x << " " << x << "\n"
#define pb push_back

const int N = 800;

struct Point {
    int x;
    int y;
};
Point a[1 + N + 1];
int oriz[1 + N + 1];
vector <int> v[1 + N];

double med;

bool inside (int x1, int x2, int y1, int y2) {
    if (x2 <= x1 && y1 <= y2)
        return true;
    if (y2 <= x1 && y1 <= x2)
        return true;
    return false;
}

double calc (Point a, Point b, double med) {
    return a.y + 1.0 * (b.y - a.y) * (med - a.x) / (b.x - a.x);
}

bool cmp (int x, int y) {
    return calc (a[x], a[x + 1], med) < calc (a[y], a[y + 1], med);
}

ll area (Point a, Point b, Point c) {
    return 1ll * a.x * b.y + 1ll * b.x * c.y + 1ll * c.x * a.y - 1ll * a.y * b.x - 1ll * b.y * c.x - 1ll * c.y * a.x;
}

bool ok;

bool check (int x, Point p) {
    ll det;
    if (a[x].x < a[x + 1].x || (a[x].x == a[x + 1].x && a[x].y < a[x + 1].y))
        det = area (a[x], a[x + 1], p);
    else
        det = area (a[x + 1], a[x], p);
    if (det == 0)
        ok = true;
    return det >= 0;
}


int main () {
    freopen ("poligon.in", "r", stdin);
    freopen ("poligon.out", "w", stdout);

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].y;
        oriz[i] = a[i].x;
    }
    a[n + 1] = a[1];

    sort (oriz + 1, oriz + n + 1);
    int nx = 0;
    oriz[0] = -1;
    for (int i = 1; i <= n; i++)
        if (oriz[nx] != oriz[i])
            oriz[++nx] = oriz[i];
    oriz[nx + 1] = oriz[nx] + 100000;

    for (int i = 1; i <= nx; i++) {
        for (int j = 1; j <= n; j++)
            if (inside (oriz[i], a[j].x, oriz[i + 1], a[j + 1].x))
                v[i].pb (j);
        med = (oriz[i] + oriz[i + 1]) / 2.0;
        sort (v[i].begin (), v[i].end (), cmp);
    }

    int ans = 0;
    for (int i = 1; i <= m; i++) {
        Point p;
        cin >> p.x >> p.y;

        int l = 1, r = nx;
        int best = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (oriz[mid] < p.x)
                best = mid, l = mid + 1;
            else
                r = mid - 1;
        }

        int nr = -1;
        l = 0, r = v[best].size () - 1;
        ok = false;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (check (v[best][mid], p))
                nr = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        if (nr % 2 == 0 || ok)
            ans++;
    }

    cout << ans << "\n";
    return 0;
}