Pagini recente » Cod sursa (job #1021302) | Cod sursa (job #199747) | Cod sursa (job #199791) | Cod sursa (job #1624463) | Cod sursa (job #3295513)
#include <fstream>
#include <vector>
using namespace std;
struct Point {
int x, y;
};
bool onSegment(Point a, Point b, Point p) {
long long cross = 1LL * (b.x - a.x) * (p.y - a.y) - 1LL * (b.y - a.y) * (p.x - a.x);
if (cross != 0) return false;
return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}
bool insidePolygon(const vector<Point>& poly, const Point& p) {
int cnt = 0;
int n = poly.size();
for (int i = 0; i < n; ++i) {
Point a = poly[i];
Point b = poly[(i + 1) % n];
if (onSegment(a, b, p))
return true;
if (a.y > b.y)
swap(a, b);
// Verifică dacă muchia intersectează linia orizontală de la p
if (p.y > a.y && p.y <= b.y) {
long long dx = b.x - a.x;
long long dy = b.y - a.y;
long long cmp = 1LL * dx * (p.y - a.y) - 1LL * dy * (p.x - a.x);
if (cmp > 0)
cnt++;
}
}
return cnt % 2 == 1;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int N, M;
fin >> N >> M;
vector<Point> poly(N);
for (int i = 0; i < N; ++i)
fin >> poly[i].x >> poly[i].y;
int rez = 0;
for (int i = 0; i < M; ++i) {
Point p;
fin >> p.x >> p.y;
if (insidePolygon(poly, p))
++rez;
}
fout << rez << '\n';
return 0;
}