Pagini recente » Cod sursa (job #1482358) | Cod sursa (job #1934623) | Cod sursa (job #3327260) | Cod sursa (job #3297874) | Cod sursa (job #3357165)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
struct Point {
long long x, y;
};
// Structura pentru a retine o latura si bounding box-ul ei pe Y
struct Edge {
Point a, b;
long long minY, maxY;
long long minX, maxX;
};
// Verifica rapid daca P poate fi pe segmentul AB
inline bool isOnSegment(const Point& p, const Point& a, const Point& b, const Edge& edge) {
// Daca P e in afara cutiei delimitate de segment, nu e pe segment
if (p.x < edge.minX || p.x > edge.maxX || p.y < edge.minY || p.y > edge.maxY) {
return false;
}
// Verificare coliniaritate
long long crossProduct = (p.y - a.y) * (b.x - a.x) - (p.x - a.x) * (b.y - a.y);
return crossProduct == 0;
}
int main() {
// Optimizare maxima pentru I/O standard
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> v(n);
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
// Pre-calculam laturile si limitele lor pentru a nu repeta operatiile in bucla mare
vector<Edge> edges(n);
for (int i = 0; i < n; ++i) {
edges[i].a = v[i];
edges[i].b = v[(i + 1) % n];
edges[i].minY = min(edges[i].a.y, edges[i].b.y);
edges[i].maxY = max(edges[i].a.y, edges[i].b.y);
edges[i].minX = min(edges[i].a.x, edges[i].b.x);
edges[i].maxX = max(edges[i].a.x, edges[i].b.x);
}
int validCrimes = 0;
Point p;
// Procesam cele M puncte
for (int i = 0; i < m; ++i) {
fin >> p.x >> p.y;
int intersectCount = 0;
bool onBoundary = false;
for (int j = 0; j < n; ++j) {
// 1. Quick check: daca schita Y a laturii nu intersecteaza nivelul p.y, trecem mai departe
if (p.y < edges[j].minY || p.y > edges[j].maxY) {
continue;
}
// 2. Verificam daca e pe margine
if (isOnSegment(p, edges[j].a, edges[j].b, edges[j])) {
onBoundary = true;
break; // Daca e pe margine, stim sigur ca e valid, nu mai numaram
}
// 3. Ray casting strict pentru laturile ramase
// Conditia stricta de intersectie (folosind conventia jumatatii deschise de interval)
if ((edges[j].a.y <= p.y && edges[j].b.y > p.y) || (edges[j].b.y <= p.y && edges[j].a.y > p.y)) {
long long cross = (p.y - edges[j].a.y) * (edges[j].b.x - edges[j].a.x);
long long deltaY = edges[j].b.y - edges[j].a.y;
if (deltaY > 0 && cross >= (p.x - edges[j].a.x) * deltaY) {
intersectCount++;
} else if (deltaY < 0 && cross <= (p.x - edges[j].a.x) * deltaY) {
intersectCount++;
}
}
}
if (onBoundary || (intersectCount % 2 != 0)) {
validCrimes++;
}
}
fout << validCrimes << "\n";
fin.close();
fout.close();
return 0;
}