Pagini recente » Atasamentele paginii Profil Sherby | Borderou de evaluare (job #3111132) | Cod sursa (job #2638032) | Borderou de evaluare (job #2634421) | Cod sursa (job #3319588)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge {
int x1,y1,x2,y2;
int ymin, ymax;
int dx, dy;
};
inline ll detll(int x1,int y1,int x2,int y2,int x3,int y3){
return 1LL*(x2-x1)*(y3-y1) - 1LL*(y2-y1)*(x3-x1);
}
inline bool on_segment(const Edge &e, int px, int py){
// check collinear + bounding box
if (detll(e.x1,e.y1,e.x2,e.y2,px,py) != 0) return false;
if (px < min(e.x1,e.x2) || px > max(e.x1,e.x2)) return false;
if (py < min(e.y1,e.y2) || py > max(e.y1,e.y2)) return false;
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// folosim scanf/printf pentru viteza I/O
int n, m;
if (scanf("%d %d", &n, &m) != 2) return 0;
vector<int> vx(n+1), vy(n+1);
for(int i=1;i<=n;i++) scanf("%d %d", &vx[i], &vy[i]);
// close polygon
vx.push_back(vx[1]); vy.push_back(vy[1]);
// parametri bucketing
const int BLOCK = 128; // dimensiune bloc (ajustabil) -> 60000/128 ≈ 469 blocuri
const int YMAX = 60000;
int nblocks = (YMAX / BLOCK) + 2;
vector<vector<int>> bucket(nblocks);
vector<Edge> edges;
edges.reserve(n);
for(int i=1;i<=n;i++){
Edge e;
e.x1 = vx[i];
e.y1 = vy[i];
e.x2 = (i==n ? vx[1] : vx[i+1]);
e.y2 = (i==n ? vy[1] : vy[i+1]);
e.dx = e.x2 - e.x1;
e.dy = e.y2 - e.y1;
e.ymin = min(e.y1, e.y2);
e.ymax = max(e.y1, e.y2);
int id = edges.size();
edges.push_back(e);
// daca muchia e orizontala, o ignoram pentru ray-crossing (dar o vom verifica la on-segment)
if (e.ymin == e.ymax) continue;
int b1 = e.ymin / BLOCK;
int b2 = (e.ymax - 1) / BLOCK; // half-open [ymin, ymax)
if (b2 >= nblocks) b2 = nblocks-1;
for(int b = b1; b <= b2; ++b){
bucket[b].push_back(id);
}
}
int ans = 0;
for(int qi=0; qi<m; ++qi){
int px, py;
scanf("%d %d", &px, &py);
int b = py / BLOCK;
if (b < 0) b = 0;
if (b >= nblocks) b = nblocks-1;
bool onEdge = false;
int crosses = 0;
// iterate doar muchiile din bucket-ul blocului y
const vector<int> &vec = bucket[b];
for(int idx : vec){
const Edge &e = edges[idx];
// daca punctul y nu e in intervalul [ymin, ymax) -> nu intersecteaza
if (!(e.ymin <= py && py < e.ymax)) continue;
// verificare pe segment (inclusiv muchii orizontale care nu sunt in bucket)
// dar on_segment trebuie verificat și pentru muchiile orizontale (pe care nu le-am pus in bucket)
if (on_segment(e, px, py)) { onEdge = true; break; }
// acum calculam daca intersectia cu linia y=py se afla la x > px
// evitam impartirea: comparam (px - x1) * dy cu dx * (py - y1)
ll left = 1LL*(px - e.x1) * e.dy;
ll right = 1LL*e.dx * (py - e.y1);
if (e.dy > 0) {
if (left < right) crosses++;
} else { // e.dy < 0
if (left > right) crosses++;
}
}
// trebuie in plus sa verificam daca punctul sta exact pe vreo muchie orizontala,
// deoarece pentru muchiile orizontale nu am pus in bucket. Verificarea completa de
// on-segment pe toate muchiile ar fi scumpa; dar putem verifica vârfurile vecine
// (N mici = 800): verificare rapida a tuturor muchiilor doar pentru cazurile rare:
if (!onEdge){
// verificare rapida pe toate muchiile orizontale sau cele care nu erau in bucket
// (aceasta verificare e rară în mod normal; N=800 e acceptabil)
for(const Edge &e : edges){
if (on_segment(e, px, py)){ onEdge = true; break; }
}
}
if (onEdge) ++ans;
else if (crosses & 1) ++ans;
}
printf("%d", ans);
return 0;
}