Pagini recente » Cod sursa (job #430211) | Cod sursa (job #877167) | Cod sursa (job #2751500) | Cod sursa (job #1217389) | Cod sursa (job #1968600)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("poligon.in");
ofstream fo("poligon.out");
using f64 = double;
const f64 C = cos(1.3241), S = sin(1.3241), EPS = 1e-7;
const int N = 805;
struct Ptx {
f64 x, y;
Ptx rot() {
f64 nx = x * C + y * S, ny = y * C - x * S;
x = nx, y = ny;
return *this; }
inline bool operator < (const Ptx &arg) const {
return x < arg.x; }
inline bool operator > (const Ptx &arg) const {
return x > arg.x; }
inline bool operator == (const Ptx &arg) const {
return abs(x - arg.x) < EPS && abs(y - arg.y) < EPS; } };
struct Seg {
f64 a, b;
inline Seg() { }
inline Seg(const Ptx &v, const Ptx &w) {
a = (v.y - w.y) / (v.x - w.x);
b = v.y - a * v.x; }
inline f64 operator [] (const f64 &x) const {
return x * a + b; }
inline bool operator < (const Ptx &arg) const {
return arg.y > arg.x * a + b; }
inline bool operator > (const Ptx &arg) const {
return arg.y < arg.x * a + b; }
inline bool operator == (const Ptx &arg) const {
return abs(arg.y - (arg.x * a + b)) < EPS; } };
vector<Seg> str[N];
vector<Ptx> pts;
vector<int> srt;
int n, m;
void get_strips() {
Ptx x, y;
srt.resize(n);
iota(begin(srt), end(srt), 0);
sort(begin(srt), end(srt), [pts](int a, int b) {
return pts[a] < pts[b]; });
for (int i = 1; i < n; ++i) {
x = pts[srt[i - 1]];
y = pts[srt[i]];
for (int j = 0; j < n; ++j)
if (min(pts[j], pts[(j + 1) % n]).x - EPS < x.x && y.x < max(pts[j], pts[(j + 1) % n]).x + EPS)
str[i].emplace_back(pts[j], pts[(j + 1) % n]);
sort(begin(str[i]), end(str[i]), [x = pts[srt[i - 1]].x, px = pts[srt[i]].x](const Seg &a, const Seg &b) {
return (abs(a[x] - b[x]) < EPS) ? (a[px] < b[px]) : (a[x] < b[x]); }); } }
bool in(Ptx arg) {
int strip = -1, line = -1;
if (arg < pts[srt.front()])
return false;
if (arg > pts[srt.back()])
return false;
for (int msk = 1 << 10; msk; msk>>= 1)
if (strip + msk < n && pts[srt[strip + msk]].x < arg.x)
strip+= msk;
++strip;
for (int msk = 1 << 10; msk; msk>>= 1)
if (line + msk < str[strip].size() && str[strip][line + msk] < arg)
line+= msk;
if (line % 2 == 0)
return true;
if (line >= 0 && str[strip][line] == arg)
return true;
if (line + 1 < str[strip].size() && str[strip][line + 1] == arg)
return true;
return false; }
int main() {
int ant = 0;
Ptx p;
fi >> n >> m;
pts.resize(n);
for (auto &i: pts) {
fi >> i.x >> i.y;
i.x+= 1.0, i.y+= 1.0;
i.rot(); }
get_strips();
while (m--) {
fi >> p.x >> p.y;
p.x+= 1.0, p.y+= 1.0;
ant+= in(p.rot()) ? 1 : 0; }
fo << ant << '\n';
return 0; }