Pagini recente » Cod sursa (job #2220442) | Cod sursa (job #865036) | Cod sursa (job #886405) | Cod sursa (job #1840534) | Cod sursa (job #3357164)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
long long x, y;
};
// Verifica daca punctul P se afla pe segmentul AB
bool isOnSegment(Point p, Point a, Point b) {
// Verificare coliniaritate folosind produsul vectorial (cross product)
long long crossProduct = (p.y - a.y) * (b.x - a.x) - (p.x - a.x) * (b.y - a.y);
if (crossProduct != 0) {
return false;
}
// Verificare daca P este in interiorul cutiei delimitate de A si B
return p.x >= min(a.x, b.x) && p.x <= max(a.x, b.x) &&
p.y >= min(a.y, b.y) && p.y <= max(a.y, b.y);
}
// Verifica daca punctul este inside sau pe marginea poligonului
bool isInsideOrOnBoundary(Point p, const vector<Point>& polygon, int n) {
int intersectCount = 0;
for (int i = 0; i < n; ++i) {
Point a = polygon[i];
Point b = polygon[(i + 1) % n]; // Urmatorul varf (inchide poligonul)
// Daca punctul e pe margine, returnam direct true
if (isOnSegment(p, a, b)) {
return true;
}
// Ray casting: tragem o raza spre dreapta de la P
// Verificam daca segmentul AB intersecteaza linia orizontala y = p.y
if ((a.y <= p.y && b.y > p.y) || (b.y <= p.y && a.y > p.y)) {
// Calculam coordonata X a intersectiei segmentului cu dreapta y = p.y
// Folosim inmultire in loc de impartire pentru a evita float/double
// x_intersect = a.x + (p.y - a.y) * (b.x - a.x) / (b.y - a.y)
long long cross = (p.y - a.y) * (b.x - a.x);
long long deltaY = b.y - a.y;
// Verificam daca punctul de intersectie este la dreapta lui p.x
// Trebuie sa fim atenti la semnul lui deltaY
if (deltaY > 0 && cross >= (p.x - a.x) * deltaY) {
intersectCount++;
} else if (deltaY < 0 && cross <= (p.x - a.x) * deltaY) {
intersectCount++;
}
}
}
// Daca numarul de intersectii este impar, punctul este inauntru
return (intersectCount % 2 != 0);
}
int main() {
// Optimizare pentru operatiile de I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int n, m;
if (!(fin >> n >> m)) return 0;
vector<Point> polygon(n);
for (int i = 0; i < n; ++i) {
fin >> polygon[i].x >> polygon[i].y;
}
int validCrimes = 0;
for (int i = 0; i < m; ++i) {
Point p;
fin >> p.x >> p.y;
if (isInsideOrOnBoundary(p, polygon, n)) {
validCrimes++;
}
}
fout << validCrimes << "\n";
fin.close();
fout.close();
return 0;
}