Pagini recente » Cod sursa (job #2259652) | Cod sursa (job #1938930) | Cod sursa (job #2327733) | Cod sursa (job #1765421) | Cod sursa (job #552305)
Cod sursa(job #552305)
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 805
#define y first
#define x second
#define y1 first
#define y2 second
#define mp make_pair
using namespace std;
typedef pair <int, int> ii;
typedef pair <double, int> interval;
int n, m, nintr, nrsegm [nmax];
ii p [nmax];
ii intr [nmax];
interval segm [nmax] [nmax];
void scan ()
{
int i;
scanf ("%d%d", &n, &m);
for (i=1; i <= n; ++i)
scanf ("%d%d", &p [i].x, &p [i].y);
}
double xmijloc (int p1, int p2)
{
double mx;
mx=((double)p [p1].x + p [p2].x)/2;
return mx;
}
void bucatele ()
{
int i, j;
sort (p+1, p+1+n);
for (i=1; i < n; ++i)
{
j=i+1;
while (j < n && p [j+1].y == p [j].y)
++j;
intr [++nintr]=ii (p [i].y, p [j].y);
i=j;
}
for (i=1; i <= nintr; ++i)
{
for (j=1; j < n; ++j)
{
if (p [j].y < intr [i].y1 || p [j].y > intr [i].y2) continue;
if (p [j+1].y < intr [i].y1 || p [j+1].y > intr [i].y2) continue;
segm [i] [++nrsegm [i]]= (mp (xmijloc (j, j+1), j));
}
sort (segm [i]+1, segm [i]+1+nrsegm [1]);
}
}
bool exista (ii punct)
{
int s=1<<10, i;
for (i=0; s; s >>= 1)
{
if (n < i+s) continue;
if (punct.y < p [i+s].y) continue;
if (punct.y == p [i+s].y && punct.x < p [i+s].x) continue;
i+=s;
}
if (p [i] == punct) return true;
return false;
}
int semn (ii punct, int ind)
{
return (p [ind].x-punct.x)*(p [ind+1].y-punct.y)-(p [ind+1].x-punct.x)*(p [ind].y-punct.y);
}
int cb1 (int yy)
{
int s=1<<10, i;
for (i=0; s; s >>= 1)
if (nintr >= i+s && intr [i+s].y1 <= yy)
i+=s;
return i-1;
}
int cb2 (ii punct, int k)
{
if (semn (punct, segm [k] [1].second) < 0) return 0;
if (semn (punct, segm [k] [nrsegm [k]].second) > 0) return 0;
int s=1<<10, i;
for (i=0; s; s >>= 1)
{
if (nrsegm [k] < i+s) continue;
if (semn (punct, segm [k] [i+s].second) <= 0)
i+=s;
}
if (semn (punct, segm [k] [i+s].second) == 0) return 1;
return i;
}
bool interior (ii punct)
{
if (exista (punct))
return true;
if (punct.y < intr [1].y1 || punct.y > intr [nintr].y2) return false;
int k=cb1 (punct.y);
if (cb2 (punct, k) % 2 == 1)
return true;
return false;
}
int rez ()
{
int i, num=0;
ii punct;
for (i=1; i <= m; ++i)
{
scanf ("%d%d", &punct.x, &punct.y);
if (interior (punct))
++num;
}
return num;
}
int main ()
{
freopen ("poligon.in", "r", stdin);
freopen ("poligon.out", "w", stdout);
scan ();
bucatele ();
printf ("%d\n", rez ());
return 0;
}