Pagini recente » Cod sursa (job #2181363) | Cod sursa (job #1357239) | Cod sursa (job #3277766) | Cod sursa (job #2897526) | Cod sursa (job #1947800)
#include <cstdio>
#include <algorithm>
#include <vector>
#define pii pair <int, int>
#define f first
#define s second
using namespace std;
int n, m;
pii v[1024], ban[1024], sor[1024];
vector <pii> segm[1024];
bool cmp (pii a, pii b)
{
int ma = (v[a.f].s + v[a.s].s) / 2;
int mb = (v[b.f].s + v[b.s].s) / 2;
return ma < mb;
}
int det (pii a, pii b, pii c)
{
long long rez = 1LL * (a.f - c.f) * (b.s - a.s) + 1LL * (a.s - c.s) * (a.f - b.f);
if (!rez) return 0;
if (rez > 0LL) return 1;
return -1;
}
int finb (int a)
{
int st = 1, dr = n, poz = 0;
for (; st <= dr;)
{
int mij = (st + dr) >> 1;
if (ban[mij].f <= a && a <= ban[mij].s)
{
if (a == ban[mij].f) poz = mij, dr = mij - 1;
else return mij;
continue;
}
if (ban[mij].f > a) dr = mij - 1;
else st = mij + 1;
}
return poz;
}
int fins (pii a, int i)
{
int st = 0, dr = segm[i].size () - 1, poz = -1;
for (; st <= dr;)
{
int mij = (st + dr) >> 1;
int rez = det (a, v[segm[i][mij].f], v[segm[i][mij].s]);
if (!rez) return -100;
if (rez > 0) poz = mij, st = mij + 1;
else dr = mij - 1;
}
return poz;
}
int main ()
{
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
scanf ("%d %d", &n, &m);
for (int i = 1; i <= n; ++i)
scanf ("%d %d", &v[i].f, &v[i].s),
sor[i] = v[i];
v[n + 1] = v[1];
v[0] = v[n];
sort (sor + 1, sor + n + 1);
int lst = 0;
for (int in = 1; in < n; ++in)
{
if (sor[in].f == sor[in + 1].f) continue;
int j = ++lst;
ban[j] = {sor[in].f, sor[in + 1].f};
for (int i = 1; i <= n; ++i)
{
if (min (v[i].f, v[i + 1].f) <= ban[j].f && ban[j].s <= max (v[i].f, v[i + 1].f))
{
if (v[i].f < v[i + 1].f) segm[j].push_back ({i, i + 1});
else segm[j].push_back ({i + 1, i});
}
}
sort (segm[j].begin (), segm[j].end (), cmp);
}
n = lst;
int rez = 0;
for (; m; --m)
{
int a, b;
scanf ("%d %d", &a, &b);
int i = finb (a);
if (i < 1) continue;
int j = fins (pii (a, b), i);
if (j == -100)
{
++rez;
continue;
}
if (j < 0 || j >= segm[i].size ()) continue;
if ((j + 1) & 1) ++rez;
}
printf ("%d\n", rez);
return 0;
}