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.
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.
Na standardni izlaz ispisati broj ribica koje se ne nalaze u jezeru.
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
1
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) {
.y += EPS;
P}
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;
<Point> poly(n + 1);
vectorfor (int i = 0; i < n; i++) {
>> poly[i].x >> poly[i].y;
cin }
[n] = poly[0];
poly
<Point> P(m);
vectorfor (int i = 0; i < m; i++) {
>> P[i].x >> P[i].y;
cin }
int count = 0;
for (int i = 0; i < m; i++) {
if (!ray_casting(poly, P[i])) {
++;
count}
}
<< count << endl;
cout
return 0;
}