Ribice

U jezeru i okolini se nalaze ribice. Neke od njih se nalaze u jezeru, dok su druge (upecane) nalaze na suvom. Odrediti broj ribica na suvom, ukoliko znamo poziciju svake ribice, kao i temena poligona koji predstavlja jezero.

Opis ulaza

Sa standardnog ulaza se unosi broj temena jezera \(n\), a zatim i broj ribica \(m\). Nakon toga, se unose redom \(n\) temena jezera, koja su data sa dve koordinate \(x, y\). Odmah zatim, se unose redom \(m\) pozicija ribica, koja su, takođe, data sa dve koordinate \(x, y\).

Opis izlaza

Na standardni izlaz ispisati broj ribica koje se ne nalaze u jezeru.

Primer

Ulaz

12 3
0 0
0 1
0 2
1 2
2 2
3 2
3 1
3 0
2 0
2 1
1 1
1 0
4 4
0.5 0.5
2.5 0.5

Izlaz

1

Rešenje

Opis glavnog rešenja

U ovom bloku se opisuje glavno rešenje zadatka.

#include <iostream>
#include <vector>
#include <cmath>

#define EPS 1.0E-9

using namespace std;

struct Point {
    double x;
    double y;
};

bool ray_intersect(const Point& A, const Point &B, Point P)
{
    if (P.y == A.y || P.y == B.y) {
        P.y += EPS;
    }
    
    if (P.y < A.y || P.y > B.y) {
        return false;
    }

    if (P.x > max(A.x, B.x)) {
        return false;
    }

    if (P.x < min(A.x, B.x)) {
        return true;
    }

    const auto k_AB = (B.y - A.y) / (B.x - A.x);
    const auto k_AP = (P.y - A.y) / (P.x - A.x);

    return k_AP >= k_AB;
}

bool ray_casting(const vector<Point> &poly, const Point &P)
{
    int count = 0;

    for (int i = 0; i < poly.size() - 1; i++) {
        const auto &A = poly[i];
        const auto &B = poly[i + 1];

        if (A.y < B.y) {
            if (ray_intersect(A, B, P)) {
                count++;
            }
        } else {
            if (ray_intersect(B, A, P)) {
                count++;
            }
        }
    }

    return count % 2;
}

int main() 
{
    int n, m; cin >> n >> m;

    vector<Point> poly(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> poly[i].x >> poly[i].y;
    }
    poly[n] = poly[0];

    vector<Point> P(m);
    for (int i = 0; i < m; i++) {
        cin >> P[i].x >> P[i].y;
    }

    int count = 0;
    for (int i = 0; i < m; i++) {
        if (!ray_casting(poly, P[i])) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}