Pagini recente » Cod sursa (job #1246291) | Cod sursa (job #1163914) | Cod sursa (job #2675431) | Cod sursa (job #3237397) | Cod sursa (job #2173257)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#define x first
#define y second
using namespace std;
const int MAXN = 8e2;
const int MAXCOORD = 6e4 + 10;
const int LGP2 = 10;
typedef pair <int, int> Point;
typedef pair <Point, Point> Segment;
Point pts[MAXN + 1];
vector <int> vert[MAXCOORD], xcoord;
vector <int> reg[MAXN + 3];
double aux;
int cln;
inline long long det(Point A, Point B, Point C) {
return 1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y - 1LL * A.y * B.x - 1LL * B.y * C.x - 1LL * C.y * A.x;
}
inline double sg_cmp(Point A, Point B, double x) {
return A.y + (B.y - A.y) * (aux - A.x) / (1.0 * B.x - A.x);
}
bool cmp(int A, int B) {
return sg_cmp(pts[A], pts[A + 1], aux) < sg_cmp(pts[B], pts[B + 1], aux);
}
inline int bin_src_cmp(int ind, Point P) {
long long tmp = det(min(pts[ind], pts[ind + 1]), max(pts[ind], pts[ind + 1]), P);
if (tmp == 0)
cln = 1;
return (tmp >= 0);
}
inline int input_point(Point P, int n) {
int pos = 0;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (pos + step < n && pts[pos + step] <= P)
pos += step;
return (pts[pos] == P);
}
inline int on_vertical_shit(Point P) {
int pos = -1;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (pos + step < (int) vert[P.x].size() && vert[P.x][pos + step] <= P.y)
pos += step;
++pos;
return ((pos & 1) || (pos > 0 && vert[P.x][pos - 1] == P.y));
}
inline int check_reg(Point P, int region) {
if (region <= 0 || P.x > xcoord[region + 1])
return 0;
cln = 0;
int pos = -1;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (pos + step < (int) reg[region].size() && bin_src_cmp(reg[region][pos + step], P))
pos += step;
++pos;
return (cln || (pos & 1));
}
int main()
{
int n, m;
ifstream fin("poligon.in");
fin >> n >> m;
xcoord.resize(n + 2);
for (int i = 0; i < n; ++i) {
fin >> pts[i].x >> pts[i].y;
xcoord[i + 1] = pts[i].x;
}
pts[n] = pts[0];
xcoord[0] = -MAXCOORD;
xcoord[n + 1] = MAXCOORD;
sort(xcoord.begin(), xcoord.end());
auto last = unique(xcoord.begin(), xcoord.end());
xcoord.erase(last, xcoord.end());
for (int i = 0; i < n; ++i)
if (pts[i].x == pts[i + 1].x) {
vert[pts[i].x].push_back(pts[i].y);
vert[pts[i].x].push_back(pts[i + 1].y);
}
for (int i = 1; i < (int) xcoord.size() - 1; ++i)
sort(vert[xcoord[i]].begin(), vert[xcoord[i]].end());
for (int i = 0; i < (int) xcoord.size() - 1; ++i) {
for (int j = 0; j < n; ++j)
if ((pts[j].x <= xcoord[i] && xcoord[i + 1] <= pts[j + 1].x) || (pts[j + 1].x <= xcoord[i] && xcoord[i + 1] <= pts[j].x))
reg[i].push_back(j);
aux = (xcoord[i] + xcoord[i + 1]) / 2.0;
sort(reg[i].begin(), reg[i].end(), cmp);
}
int ans = 0;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
if (on_vertical_shit({x, y}) || input_point({x, y}, n))
++ans;
else if (xcoord[1] <= x && x <= xcoord[(int) xcoord.size() - 2]){
int r = 0;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (step + r < (int) xcoord.size() && xcoord[step + r] <= x)
r += step;
ans += (check_reg({x, y}, r - 1) || check_reg({x, y}, r));
}
}
fin.close();
ofstream fout("poligon.out");
fout << ans;
fout.close();
return 0;
}