U jezeru i okolini se nalaze ribe. Neke od njih se nalaze u jezeru, dok su druge (upecane) nalaze na suvom. Odrediti broj riba na suvom, ukoliko znamo poziciju svake ribe, kao i temena poligona koji predstavlja jezero.
Sa standardnog ulaza se unosi broj temena jezera \(n\), a zatim i broj riba \(m\). Nakon toga, se unose redom \(n\) temena jezera, koja su data sa dve koordinate \(x, y\). Odmah zatim, se unose redom \(m\) pozicija riba, koja su, takođe, data sa dve koordinate \(x, y\).
Na standardni izlaz ispisati broj riba 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
Za svaku ribicu potrebno je odrediti da li se nalazi unutar mnogougla koji predstavlja jezero. U ovom rešenju koristi se metoda bacanja zraka (ray casting). Kroz posmatranu tačku, tj. poziciju ribice, zamislimo polupravu koja ide vodoravno udesno. Zatim prebrojimo koliko puta ta poluprava seče stranice mnogougla. Ako je broj preseka neparan, tačka je u unutrašnjosti mnogougla, a ako je paran, tačka je van njega.
Da bi provera bila jednostavnija, niz temena jezera se na kraju
dopuni prvim temenom, pa se svaka stranica posmatra kao par uzastopnih
tačaka u nizu. Za svaku stranicu se prvo obezbeđuje da se njeni krajevi
posmatraju odozdo nagore. Ako se \(y\)
koordinata ribice poklapa sa \(y\)
koordinatom nekog temena stranice, ona se neznatno pomera za vrednost
EPS. Time se izbegava slučaj da zrak prolazi tačno kroz
teme mnogougla i da se isti presek izbroji dva puta.
Funkcija koja proverava presek najpre odbacuje stranice čiji interval \(y\) koordinata ne sadrži visinu ribice. Ako je cela stranica levo od ribice, ona ne može seći polupravu koja ide udesno. Ako je ribica levo od cele stranice, presek sigurno postoji. U preostalom slučaju porede se nagibi prave kroz stranicu i prave kroz donje teme stranice i ribicu, na osnovu čega se zaključuje da li poluprava seče datu stranicu.
Nakon što se za jednu ribicu odredi broj preseka, neparan broj znači
da je ribica u jezeru, a paran broj da je na suvom. Zato se brojač
rešenja uvećava samo za ribice za koje funkcija ray_casting
vrati da nisu u mnogouglu.
Za svaku od \(m\) ribica obilazi se svih \(n\) stranica jezera, pa je vremenska složenost algoritma \(O(mn)\). Memorijska složenost je \(O(n + m)\), jer se čuvaju temena mnogougla i pozicije svih ribica.
#include <iostream>
#include <vector>
#include <cmath>
#define EPS 1.0E-9
using namespace std;
struct Point {
double x;
double y;
};
// Funkcija koja proverava da li poluprava (zrak) koja ide desno iz tačke P
// seče duž AB
bool ray_intersect(const Point& A, const Point &B, Point P)
{
// U slučaju da zrak pogađa tačno u jedno od temena duži, pomeramo ga
// malo na gore
if (P.y == A.y || P.y == B.y) {
P.y += EPS;
}
// Slučajevi kada je duž iznad/ispod zraka
if (P.y < A.y || P.y > B.y) {
return false;
}
// Slučaj kada je duž levo od zraka
if (P.x > max(A.x, B.x)) {
return false;
}
// Slučaj kada je duž desno od zraka i sigurno ga seče
if (P.x < min(A.x, B.x)) {
return true;
}
// Ni jedna provera nije prošla, pa proveravamo koeficijente pravca
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;
// Prolazimo kroz sve stranice mnogougla
for (int i = 0; i < poly.size() - 1; i++) {
const auto &A = poly[i];
const auto &B = poly[i + 1];
// Staramo se da je A uvek ispod B
if (A.y < B.y) {
if (ray_intersect(A, B, P)) {
count++;
}
} else {
if (ray_intersect(B, A, P)) {
count++;
}
}
}
// Ako je broj preseka neparan tačka je unutra. U suprotnom je spolja
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;
}