Pagini recente » Cod sursa (job #1746558) | Cod sursa (job #963786) | Cod sursa (job #2940461) | Cod sursa (job #1175410) | Cod sursa (job #2171385)
#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 {
return x == other.x && y == other.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 (A == other.A && B == other.B)
return 0;
return det(A, B, other.A) >= 0LL && det(A, B, other.B) >= 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];
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 || pts[pos + step] == P))
pos += step;
return (pts[pos] == P);
}
inline int on_vertical_shit(Point P) {
int pv = -1;
for (int step = 1 << LGP2; step > 0; step >>= 1)
if (pv + step < (int) vert.size() && (vert[pv + step].x < P.x || (vert[pv + step].x == P.x && vert[pv + step].y2 < P.y)))
pv += step;
++pv;
return (pv < (int) vert.size() && vert[pv].x == P.x && vert[pv].y1 <= P.y && P.y <= vert[pv].y2);
}
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;
if (on_vertical_shit({x, y}))
++ans;
else if (input_point({x, y}, n))
++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;
}