Pagini recente » Cod sursa (job #3295513) | Cod sursa (job #34706) | Cod sursa (job #1897485) | Cod sursa (job #2826808) | Cod sursa (job #3295512)
#include <fstream>
#include <vector>
using namespace std;
struct Point {
int x, y;
};
bool isOnSegment(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 isInsidePolygon(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 (isOnSegment(a, b, p))
return true;
// testăm intersecția razei orizontale pornind din p cu segmentul [a,b]
if (a.y > b.y)
swap(a, b);
if (p.y > a.y && p.y <= b.y) {
long long orient = 1LL * (b.x - a.x) * (p.y - a.y) - 1LL * (b.y - a.y) * (p.x - a.x);
if (orient > 0)
++cnt;
}
}
return cnt % 2 == 1;
}
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 count = 0;
for (int i = 0; i < M; ++i) {
Point p;
fin >> p.x >> p.y;
if (isInsidePolygon(polygon, p))
++count;
}
fout << count << '\n';
return 0;
}