Pagini recente » Cod sursa (job #2661427) | Cod sursa (job #1646609) | Cod sursa (job #598542) | Cod sursa (job #2553337) | Cod sursa (job #3295511)
#include <fstream>
#include <vector>
using namespace std;
struct Point {
int x, y;
};
bool isOnSegment(Point a, Point b, Point p) {
// Determinăm dacă punctul p se află pe segmentul [a, b]
int cross = (b.x - a.x) * (p.y - a.y) - (b.y - a.y) * (p.x - a.x);
if (cross != 0) return false;
int minX = min(a.x, b.x), maxX = max(a.x, b.x);
int minY = min(a.y, b.y), maxY = max(a.y, b.y);
return (p.x >= minX && p.x <= maxX && p.y >= minY && p.y <= maxY);
}
bool isInside(const vector<Point>& poly, Point p) {
int n = poly.size();
bool inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
Point a = poly[j], b = poly[i];
// verificăm dacă este pe muchie
if (isOnSegment(a, b, p)) return true;
// Ray Casting: intersecții cu muchii
bool intersect = ((a.y > p.y) != (b.y > p.y));
if (intersect) {
double x_intersect = (double)(b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x;
if (p.x < x_intersect)
inside = !inside;
}
}
return inside;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int N, M;
fin >> N >> M;
vector<Point> polygon(N);
for (int i = 0; i < N; ++i)
fin >> polygon[i].x >> polygon[i].y;
int cnt = 0;
for (int i = 0; i < M; ++i) {
Point p;
fin >> p.x >> p.y;
if (isInside(polygon, p))
++cnt;
}
fout << cnt << '\n';
return 0;
}