Pagini recente » Cod sursa (job #1750929) | Cod sursa (job #1880475) | Cod sursa (job #2316657) | Cod sursa (job #1430447) | Cod sursa (job #1722676)
#include <bits/stdc++.h>
#define maxN 805
using namespace std;
int ans, n, m, k, b[maxN], A[maxN], B[maxN], C[maxN];
int act;
bool ok;
double sa[maxN], sb[maxN];
vector < int > V[maxN];
struct coord
{
int x, y;
} v[maxN];
bool cmp(int x, int y)
{
return (sa[x] * (b[act] + b[act + 1]) + sb[x] * 2) < (sa[y] * (b[act] + b[act + 1]) + sb[y] * 2);
}
bool Ok(int i, int x, int y)
{
if (A[i] * x + B[i] * y + C[i] == 0)
ok = 1;
return 1.00 * y >= (sa[i] * x + sb[i]);
}
int bs(int x)
{
int i = 0, p = 1 << 9;
while (p)
{
if (i + p <= k && b[i + p] < x)
i += p;
p >>= 1;
}
return i;
}
int Bs(int q, int x, int y)
{
int i = 0, p = 1 << 9, len = V[q].size();
while (p)
{
if (i + p <= len && Ok(V[q][i + p - 1], x, y))
i += p;
p >>= 1;
}
return i;
}
void read()
{
int i;
freopen("poligon.in", "r", stdin);
scanf("%d %d", &n, &m);
for (i = 1; i <= n; ++ i)
{
scanf("%d %d", &v[i].x, &v[i].y);
b[i] = v[i].x;
}
v[n + 1] = v[1];
}
void solve()
{
int i, j;
sort(b + 1, b + n + 1);
for (i = 1; i <= n; ++ i)
{
A[i] = v[i + 1].y - v[i].y;
B[i] = v[i].x - v[i + 1].x;
C[i] = -v[i].x * v[i + 1].y + v[i + 1].x * v[i].y;
sa[i] = -1.0 * A[i] / B[i];
sb[i] = -1.0 * C[i] / B[i];
if (b[i] != b[i - 1] || i == 1)
b[++ k] = v[i].x;
}
b[k + 1] = 0;
for (i = 1; i <= k; ++ i)
{
act = i;
for (j = 1; j <= n; ++ j)
if ((v[j].x > b[i] && v[j + 1].x <= b[i]) || (v[j].x <= b[i] && v[j + 1].x > b[i]))
V[i].push_back(j);
sort(V[i].begin(), V[i].end(), cmp);
}
int x, y, p, q;
while (m --)
{
scanf("%d %d", &x, &y);
if (x < b[1] || x > b[k])
continue;
ok = 0;
p = bs(x);
q = Bs(p, x, y);
if (q % 2 || ok)
++ ans;
}
}
void write()
{
freopen("poligon.out", "w", stdout);
printf("%d\n", ans);
}
int main()
{
read();
solve();
write();
return 0;
}