Pagini recente » Monitorul de evaluare | Cod sursa (job #316257) | Cod sursa (job #509469) | Monitorul de evaluare | Cod sursa (job #3319591)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
ifstream in("poligon.in");
ofstream out("poligon.out");
int n, m, ans;
pair<int, int> v[805];
int det(int x1, int y1, int x2, int y2, int x3, int y3)
{
return (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
}
int pctseg(int x1, int y1, int x2, int y2, int x3, int y3)
{
int d = det(x1, y1, x2, y2, x3, y3);
if(d == 0 && x3 >= min(x1, x2) && x3 <= max(x1, x2) && y3 >= min(y1, y2) && y3 <= max(y1, y2))
{
return 1;
}
return 0;
}
struct Edge {
int x1,y1,x2,y2;
int dx,dy;
int ymin,ymax;
};
signed main()
{
in>>n>>m;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
}
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);
}
const int YMAX = 60000;
const int BLOCK = 128;
int nblocks = (YMAX / BLOCK) + 3;
vector<vector<int>> bucket(nblocks);
vector<vector<int>> horiz(YMAX + 1);
for(int id = 0; id < (int)edges.size(); ++id)
{
Edge &e = edges[id];
if(e.ymin == e.ymax)
{
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);
}
}
ans = 0;
while(m--)
{
int px, py;
in>>px>>py;
bool onEdge = false;
int crosses = 0;
if(py >= 0 && py <= YMAX)
{
for(int id : horiz[py])
{
Edge &e = edges[id];
if(px >= min(e.x1, e.x2) && px <= max(e.x1, e.x2))
{
onEdge = true;
break;
}
}
if(onEdge)
{
ans++;
continue;
}
}
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)
{
Edge &e = edges[id];
if(!(e.ymin <= py && py < e.ymax))
{
continue;
}
if(pctseg(e.x1, e.y1, e.x2, e.y2, px, py))
{
onEdge = true;
break;
}
int left = (px - e.x1) * e.dy;
int right = e.dx * (py - e.y1);
if(e.dy > 0)
{
if(left < right)
{
crosses++;
}
}
else
{
if(left > right)
{
crosses++;
}
}
}
if(onEdge)
{
ans++;
}
else if(crosses % 2 == 1)
{
ans++;
}
}
out<<ans;
return 0;
}