Processing math: 100%

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;
}