Pagini recente » Cod sursa (job #547231) | Cod sursa (job #2926575) | Cod sursa (job #2109099) | Cod sursa (job #2644091) | Cod sursa (job #2166049)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 8e2;
const int MAXCOORD = 6e4 + 10;
const int LGP2 = 10;
struct Point {
int x, y;
bool operator < (const Point& other) const {
if (x == other.x)
return y < other.y;
return x < other.x;
}
} pts[MAXN + 1];
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;
}
struct Segment {
Point A, B;
bool operator < (const Segment& other) const {
if (det(A, B, other.A) == 0LL)
return det(A, B, other.B) > 0LL;
return det(A, B, other.A) > 0LL;
}
} v[MAXN + 1];
struct VerticalShit {
int x, y1, y2;
bool operator < (const VerticalShit& other) const {
if (x == other.x)
return y2 < other.y1;
return x < other.x;
}
};
vector <VerticalShit> vert;
struct Region {
int lft, rgh;
vector <Segment> sg;
} reg[MAXN + 3];
int main()
{
int n, m;
ifstream fin("poligon.in");
fin >> n >> m;
for (int i = 0; i < n; ++i)
fin >> pts[i].x >> pts[i].y;
pts[n] = pts[0];
for (int i = 0; i < n; ++i) {
v[i] = {pts[i], pts[i + 1]};
if (v[i].B < v[i].A)
swap(v[i].A, v[i].B);
if (v[i].A.x == v[i].B.x)
vert.push_back({v[i].A.x, v[i].A.y, v[i].B.y});
}
v[n] = {{-MAXCOORD, MAXCOORD}, {MAXCOORD, MAXCOORD}};
sort(vert.begin(), vert.end());
sort(pts, pts + n);
int num_reg = 0;
reg[num_reg].lft = -MAXCOORD;
reg[num_reg++].rgh = pts[0].x;
for (int i = 0; i < n - 1; ++i)
if (pts[i].x < pts[i + 1].x) {
reg[num_reg].lft = pts[i].x;
reg[num_reg].rgh = pts[i + 1].x;
for (int j = 0; j <= n; ++j)
if (v[j].A.x <= reg[num_reg].lft && reg[num_reg].rgh <= v[j].B.x)
reg[num_reg].sg.push_back(v[j]);
sort(reg[num_reg].sg.begin(), reg[num_reg].sg.end());
++num_reg;
}
reg[num_reg].lft = pts[n - 1].x;
reg[num_reg++].rgh = MAXCOORD;
int ans = 0;
for (int i = 0; i < m; ++i) {
int x, y;
fin >> x >> y;
int wh_reg = 0;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (wh_reg + step < num_reg && reg[wh_reg + step].lft <= x)
wh_reg += step;
int num = -1;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (num + step < (int) reg[wh_reg].sg.size() && det(reg[wh_reg].sg[num + step].A, reg[wh_reg].sg[num + step].B, {x, y}) > 0)
num += step;
++num;
int pv = -1;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (pv + step < (int) vert.size() && (vert[pv + step].x < x || (vert[pv + step].x == x && vert[pv + step].y2 < y)))
pv += step;
++pv;
int okv = (pv < (int) vert.size() && vert[pv].x == x && vert[pv].y1 <= y);
if (okv)
++ans;
else if (reg[wh_reg].sg.size())
ans += (det({x, y}, reg[wh_reg].sg[num].B, reg[wh_reg].sg[num].A) == 0LL || num % 2);
}
fin.close();
ofstream fout("poligon.out");
fout << ans;
fout.close();
return 0;
}