Pagini recente » Borderou de evaluare (job #943157) | Borderou de evaluare (job #1581073) | Borderou de evaluare (job #3308135) | Borderou de evaluare (job #2689797) | Cod sursa (job #3357166)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct Point {
int x, y; // int este suficient pentru coordonate pana la 60.000 si este mai rapid decat long long in array-uri
};
struct Edge {
Point a, b;
int minX, maxX;
};
// Vector de vectori: pentru fiecare coordonata Y de la 0 la 60000,
// retinem indicii laturilor care trec prin acel Y.
// Folosim un array static sau vector alocat global pentru viteza maxima.
vector<int> bucket[60005];
Edge edges[805];
// Verifica daca P este pe segmentul AB
inline bool isOnSegment(const Point& p, const Point& a, const Point& b, const Edge& edge) {
if (p.x < edge.minX || p.x > edge.maxX) return false;
// Cast la long long doar aici unde inmultirea poate depasi int
long long crossProduct = 1LL * (p.y - a.y) * (b.x - a.x) - 1LL * (p.x - a.x) * (b.y - a.y);
return crossProduct == 0;
}
int main() {
// Fortarea la maxim a vitezei 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> v(n);
for (int i = 0; i < n; ++i) {
fin >> v[i].x >> v[i].y;
}
// Precalculare laturi si distributie in bucket-uri
for (int i = 0; i < n; ++i) {
edges[i].a = v[i];
edges[i].b = v[(i + 1) % n];
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 minY = min(edges[i].a.y, edges[i].b.y);
int maxY = max(edges[i].a.y, edges[i].b.y);
// Adaugam latura in toate bucket-urile Y pe care le acopera
for (int y = minY; y <= maxY; ++y) {
bucket[y].push_back(i);
}
}
int validCrimes = 0;
Point p;
// Procesare interogari
for (int i = 0; i < m; ++i) {
fin >> p.x >> p.y;
// Daca Y-ul punctului este in afara hartii standard (just in case)
if (p.y < 0 || p.y > 60000) continue;
int intersectCount = 0;
bool onBoundary = false;
// Verificam DOAR laturile care stim sigur ca ating coordonata p.y
const vector<int>& activeEdges = bucket[p.y];
int numActive = activeEdges.size();
for (int j = 0; j < numActive; ++j) {
int edgeIdx = activeEdges[j];
const Edge& edge = edges[edgeIdx];
// 1. Verificare rapida margine
if (isOnSegment(p, edge.a, edge.b, edge)) {
onBoundary = true;
break;
}
// 2. Ray casting strict (conventia jumatatii de interval deschis)
if ((edge.a.y <= p.y && edge.b.y > p.y) || (edge.b.y <= p.y && edge.a.y > p.y)) {
long long cross = 1LL * (p.y - edge.a.y) * (edge.b.x - edge.a.x);
long long deltaY = edge.b.y - edge.a.y;
if (deltaY > 0 && cross >= 1LL * (p.x - edge.a.x) * deltaY) {
intersectCount++;
} else if (deltaY < 0 && cross <= 1LL * (p.x - edge.a.x) * deltaY) {
intersectCount++;
}
}
}
if (onBoundary || (intersectCount % 2 != 0)) {
validCrimes++;
}
}
fout << validCrimes << "\n";
fin.close();
fout.close();
return 0;
}