Pagini recente » Cod sursa (job #3326433) | Cod sursa (job #346824) | Cod sursa (job #755384) | Monitorul de evaluare | Cod sursa (job #3319590)
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream in("poligon.in");
ofstream out("poligon.out");
struct Edge {
int x1,y1,x2,y2;
int ymin, ymax;
int dx, dy; // x2-x1, y2-y1
};
inline long long det_ll(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){
if (det_ll(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;
}
signed main()
{
int n, m;
in >> n >> m;
vector<pair<int,int>> v(n+1);
for(int i=1;i<=n;i++){
in >> v[i].first >> v[i].second;
}
// build edges
vector<Edge> edges;
edges.reserve(n);
for(int i=1;i<=n;i++){
int j = (i==n?1:i+1);
Edge e;
e.x1 = v[i].first; e.y1 = v[i].second;
e.x2 = v[j].first; e.y2 = v[j].second;
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);
edges.push_back(e);
}
// bucketing params
const int YMAX = 60000;
const int BLOCK = 128; // ajustabil
int nblocks = (YMAX / BLOCK) + 3;
vector<vector<int>> bucket(nblocks);
vector<vector<int>> horiz(YMAX + 1); // muchii orizontale indexate dupa y
for(int id = 0; id < (int)edges.size(); ++id){
Edge &e = edges[id];
if (e.ymin == e.ymax) {
// orizontala: store by exact y
if (e.ymin >= 0 && e.ymin <= YMAX) horiz[e.ymin].push_back(id);
continue;
}
int b1 = e.ymin / BLOCK;
int b2 = (e.ymax - 1) / BLOCK;
if (b1 < 0) b1 = 0;
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;
in >> px >> py;
bool onEdge = false;
int crosses = 0;
// check horizontals at this y
if (py >= 0 && py <= YMAX){
for(int id : horiz[py]){
const Edge &e = edges[id];
if (px >= min(e.x1,e.x2) && px <= max(e.x1,e.x2)) { onEdge = true; break; }
}
if (onEdge) { ++ans; continue; }
}
// check edges from bucket
int b = py / BLOCK;
if (b < 0) b = 0;
if (b >= nblocks) b = nblocks - 1;
const vector<int> &vec = bucket[b];
for(int id : vec){
const Edge &e = edges[id];
if (!(e.ymin <= py && py < e.ymax)) continue; // not intersecting horizontal line y=py
// check if on segment (boundary)
if (on_segment(e, px, py)) { onEdge = true; break; }
// count crossing: decide if intersection x > px
// compare (px - x1) * dy ? dx * (py - y1)
long long left = 1LL*(px - e.x1) * e.dy;
long long right = 1LL*e.dx * (py - e.y1);
if (e.dy > 0) {
if (left < right) ++crosses;
} else { // e.dy < 0
if (left > right) ++crosses;
}
}
if (onEdge) ++ans;
else if (crosses & 1) ++ans;
}
out << ans;
return 0;
}