Pagini recente » Cod sursa (job #3322329) | Cod sursa (job #572161) | Monitorul de evaluare | Cod sursa (job #3322968) | Cod sursa (job #3339860)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
const int DIM = 801;
int n, m, q, x[DIM + 1];
struct pct
{
double x, y;
};
pct v[DIM + 1];
vector <int> pt[DIM + 1];
struct segm
{
pct p1, p2;
};
vector <segm> s[DIM + 1];
double det (pct a, pct b, pct c)
{
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
bool on_seg (pct a, pct b, pct p)
{
if (det (a, b, p) != 0)
return false;
if (min (a.x, b.x) <= p.x && p.x <= max (a.x, b.x) && min (a.y, b.y) <= p.y && p.y <= max (a.y, b.y))
return true;
return false;
}
int get_x (double p)
{
int l = 1, r = m, mid;
while (l <= r)
{
mid = (l + r) / 2;
if (x[mid] <= p)
l = mid + 1;
else
r = mid - 1;
}
return r;
}
bool cb (vector <segm> &v, pct p)
{
int l = 0, r = (int) v.size () - 1, mid;
while (l <= r)
{
mid = (l + r) / 2;
if (det (v[mid].p1, v[mid].p2, p) > 0)
l = mid + 1;
else
r = mid - 1;
}
return (r + 1) % 2 || on_seg (v[r].p1, v[r].p2, p);
}
void read ()
{
fin >> n >> q;
for (int i = 1; i <= n; i++)
{
fin >> v[i].x >> v[i].y;
x[i] = v[i].x;
}
v[n + 1] = v[1];
}
bool cmp (const segm &a, const segm &b)
{
return (a.p1.y + a.p2.y) > (b.p1.y + b.p2.y);
}
double calc (pct a, pct b, double x)
{
double p = (double) (b.y - a.y) * (x - a.x) / (b.x - a.x);
p += a.y;
return p;
}
void get_segm ()
{
sort (x + 1, x + n + 1);
m = 1;
for (int i = 2; i <= n; i++)
{
if (x[i] != x[i - 1])
x[++m] = x[i];
}
x[m + 1] = x[m];
for (int pos = 1; pos < m; pos++)
{
int l = x[pos], r = x[pos + 1];
for (int i = 1; i <= n; i++)
{
pct a = v[i], b = v[i + 1];
if (a.x != b.x)
{
if (a.x == l)
pt[pos].push_back (a.y);
else if (b.x == l)
pt[pos].push_back (b.y);
if (a.x > b.x)
swap (a.x, b.x);
if (a.x <= l && r <= b.x)
s[pos].push_back ({calc (a, b, l), calc (a, b, r)});
}
}
sort (s[pos].begin (), s[pos].end (), cmp);
}
}
void solve ()
{
int sol = 0;
pct p;
while (q--)
{
fin >> p.x >> p.y;
int pos = get_x (p.x);
if (p.x == x[pos] && lower_bound (pt[pos].begin (), pt[pos].end (), p.y) == pt[pos].end ())
sol++;
else if (pos > 0 && pos <= m)
sol += cb (s[pos], p);
}
fout << sol;
}
int main()
{
read ();
get_segm ();
solve ();
return 0;
}