#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <ext/hash_set>
#define MAXN 808
#define MAX_XY 60001
using namespace std;
using namespace __gnu_cxx;
typedef unsigned short uint16;
class Vector2D
{
public:
Vector2D() :
x(0),
y(0)
{}
Vector2D(const int xx, const int yy) :
x(xx),
y(yy)
{}
inline double operator % (const Vector2D& v) const
{
return ((double)x * v.y) - ((double)y * v.x);
}
inline Vector2D operator - (const Vector2D& v) const
{
return Vector2D(x - v.x, y - v.y);
}
inline Vector2D operator + (const Vector2D& v) const
{
return Vector2D(x + v.x, y + v.y);
}
inline void operator -= (const Vector2D& v)
{
x -= v.x;
y -= v.y;
}
inline void operator += (const Vector2D& v)
{
x += v.x;
y += v.y;
}
int x,y;
};
class Segment
{
public:
Segment()
{}
Segment(const Vector2D& s, const Vector2D& e) :
start(s),
end(e)
{
swapEndPoints();
}
Segment(const int x1, const int y1, const int x2, const int y2) :
start(x1, y1),
end(x2, y2)
{
swapEndPoints();
}
Vector2D start, end;
private:
inline void swapEndPoints()
{
if (start.x > end.x)
{
swap(start, end);
}
else if (start.x == end.x)
{
if (start.y > end.y)
{
swap(start, end);
}
}
}
};
inline bool ArePointsColinear
(
const Vector2D& p1,
const Vector2D& p2,
const Vector2D& p3
)
{
const Vector2D V1 = p2 - p1;
const Vector2D V2 = p3 - p1;
if ((V1 % V2) == 0)
{
return true;
}
return false;
}
inline bool SegmentProjectionContainsX(const Segment& seg, const int x)
{
if (x >= seg.start.x && x <= seg.end.x)
{
return true;
}
return false;
}
inline bool SegmentsIntersect(const Segment& seg1, const Segment& seg2)
{
const Vector2D V1 = seg1.end - seg1.start;
const Vector2D V2 = seg2.end - seg2.start;
const double crossV12 = V1 % V2;
const double crossV21 = V2 % V1;
const Vector2D diffSeg21_start = seg2.start - seg1.start;
const Vector2D diffSeg12_start = seg1.start - seg2.start;
const double crossDiffSeg21_V2 = diffSeg21_start % V2;
const double crossDiffSeg12_V1 = diffSeg12_start % V1;
// check if lines are paralel
if (0 == crossV12)
{
if (0 == crossDiffSeg21_V2) // check if lines are colinear
{
if (SegmentProjectionContainsX(seg1, seg2.start.x) ||
SegmentProjectionContainsX(seg1, seg2.end.x))
{
return true;
}
if (SegmentProjectionContainsX(seg2, seg1.start.x) ||
SegmentProjectionContainsX(seg2, seg1.end.x))
{
return true;
}
}
return false;
}
//cout << crossDiffSeg21_V2 << " " << crossV12 << endl;
const double u1 = static_cast<double>(crossDiffSeg21_V2) / crossV12;
const double u2 = static_cast<double>(crossDiffSeg12_V1) / crossV21;
//cout << u1 << " " << u2 << endl;
if (u1 >= 0 && u1 <= 1 && u2 >= 0 && u2 <= 1)
{
return true;
}
return false;
}
inline bool ComparePointsByX(const Vector2D& p1, const Vector2D& p2)
{
return p1.x < p2.x;
}
inline bool CompareSegmentsByStartX(const Segment& seg1, const Segment& seg2)
{
return seg1.start.x < seg2.start.x;
}
inline bool CompareSegmentsByStartY(const Segment& seg1, const Segment& seg2)
{
if (seg1.start.y > seg2.start.y)
{
return true;
}
else if (seg1.start.y == seg2.start.y)
{
return seg1.end.y > seg2.end.y;
}
return false;
}
inline int GetCompactPoint(const int x, const int y)
{
return ((x<<16) | y);
}
Vector2D vPoints[MAXN];
Segment vSegments[MAXN];
vector<Segment> vStrips[MAXN];
vector<Segment> vFringeSegments[MAXN];
hash_set<int> hsPoints;
inline int FindStrip(const int px, const int numStrips)
{
int step = 1;
while (step <= numStrips)
{
step <<= 1;
}
int i=0;
for (i=0; step>0; step >>= 1)
{
if (i+step < numStrips && vPoints[i+step].x <= px)
{
i += step;
}
}
if (i==0 && px < vPoints[0].x)
{
// We were to the left of the furthest left strip.
// This means we're surely not inside the polygon.
return -1;
}
else if (i==numStrips-1 && px > vPoints[numStrips-1].x)
{
// We were to the right of the furthest right strip.
// This means we're surely not inside the polygon.
return -2;
}
return i;
}
inline int GetNumberOfIntersections(const Segment& seg, const vector<Segment>& vSegments)
{
int step = 1;
const int size = vSegments.size();
while (step <= size)
{
step <<= 1;
}
int i=0;
for (i=0; step>0; step >>= 1)
{
if (i+step < size && SegmentsIntersect(seg, vSegments[i+step]))
{
i += step;
}
}
if (size && seg.start.y <= vSegments[i].start.y)
{
return i;
}
return -1;
}
inline int GetFringeSegment(const Vector2D& p, const vector<Segment>& vFringeSegments)
{
int step = 1;
const int size = vFringeSegments.size();
while (step <= size)
{
step <<= 1;
}
int i=0;
for (i=0; step>0; step >>= 1)
{
if (i+step < size && p.y>=vFringeSegments[i+step].start.y && p.y<=vFringeSegments[i+step].end.y)
{
i += step;
}
}
if (size && p.y>=vFringeSegments[i].start.y && p.y<=vFringeSegments[i].end.y)
{
return i;
}
return -1;
}
int main()
{
int n, m, incedPoints=0;
fstream fin("poligon.in", fstream::in);
fstream fout("poligon.out", fstream::out);
fin >> n >> m;
//cout << n << " " << m << "\n";
int x, y;
fin >> x >> y;
vPoints[0] = Vector2D(x,y);
for (int i=1; i<n; ++i)
{
fin >> x >> y;
hsPoints.insert(GetCompactPoint(x, y));
vPoints[i] = Vector2D(x,y);
vSegments[i-1] = Segment(vPoints[i-1], vPoints[i]);
}
vSegments[n-1] = Segment(vPoints[0], vPoints[n-1]);
sort(vPoints, vPoints+n, &ComparePointsByX);
sort(vSegments, vSegments+n, &CompareSegmentsByStartX);
for (int i=0; i<n; ++i)
{
for (int j=0; vSegments[j].start.x <= vPoints[i].x && j<n; ++j)
{
if (vPoints[i].x < vSegments[j].end.x)
{
vStrips[i].push_back(vSegments[j]);
}
else if (vPoints[i].x == vSegments[j].start.x && vPoints[i].x == vSegments[j].end.x)
{
vFringeSegments[i].push_back(vSegments[j]);
}
}
sort(vStrips[i].begin(), vStrips[i].end(), &CompareSegmentsByStartY);
sort(vFringeSegments[i].begin(), vFringeSegments[i].end(), &CompareSegmentsByStartY);
}
/*for (int i=0; i<n; ++i)
{
cout << "(" << vPoints[i].x << " " << vPoints[i].y << ") --> ";
for (uint16 j=0; j<vStrips[i].size(); ++j)
{
cout << "(" << vStrips[i][j].start.x << " " << vStrips[i][j].start.y << " "
<< vStrips[i][j].end.x << " " << vStrips[i][j].end.y << ") ";
}
cout << "\n--> ";
for (uint16 j=0; j<vFringeSegments[i].size(); ++j)
{
cout << "(" << vFringeSegments[i][j].start.x << " " << vFringeSegments[i][j].start.y << " "
<< vFringeSegments[i][j].end.x << " " << vFringeSegments[i][j].end.y << ") ";
}
cout << "\n\n";
}*/
for (int i=0; i<m; ++i)
{
fin >> x >> y;
if (hsPoints.find(GetCompactPoint(x, y)) != hsPoints.end())
{
//cout << "Inside: Is a point\n";
incedPoints++;
}
else
{
const Vector2D p(x,y);
const int indexStrip = FindStrip(p.x, n);
//cout << "Index = " << indexStrip;
if (indexStrip >= 0)
{
const Segment rayPoint(p, Vector2D(p.x, MAX_XY));
if (vPoints[indexStrip].x == p.x)
{
const int lineIndex = GetFringeSegment(p, vFringeSegments[indexStrip]);
if (lineIndex == -1)
{
const int indexLastLine = GetNumberOfIntersections(rayPoint, vStrips[indexStrip]);
if (indexLastLine >= 0)
{
if (ArePointsColinear(vStrips[indexStrip][indexLastLine].start, vStrips[indexStrip][indexLastLine].end, p))
{
//cout << "\nInside: 1) Point lies on very last line";
incedPoints++;
}
else
{
//cout << ((indexLastLine+1)%2 ? "\nInside\n" : "\nOutside\n");
if ((indexLastLine+1)%2 != 0)
{
incedPoints++;
}
}
/*cout << "\n1) Last line index = " << indexLastLine << endl;
cout << vStrips[indexStrip][indexLastLine].start.x << " " << vStrips[indexStrip][indexLastLine].start.y << endl;
cout << vStrips[indexStrip][indexLastLine].end.x << " " << vStrips[indexStrip][indexLastLine].end.y << endl;*/
}
}
else
{
//cout << "\nInside: Fringe Line Index = " << lineIndex << endl;
incedPoints++;
}
}
else
{
//cout << " " << vPoints[indexStrip].x << " " << vPoints[indexStrip].y << endl;
const int indexLastLine = GetNumberOfIntersections(rayPoint, vStrips[indexStrip]);
if (indexLastLine >= 0)
{
if (ArePointsColinear(vStrips[indexStrip][indexLastLine].start, vStrips[indexStrip][indexLastLine].end, p))
{
//cout << "\nInside: 2) Point lies on very last line";
incedPoints++;
}
else
{
//cout << ((indexLastLine+1)%2 ? "Inside\n" : "Outside\n");
if ((indexLastLine+1)%2 != 0)
{
incedPoints++;
}
}
/*cout << "\n2) Last line index = " << indexLastLine << endl;
cout << vStrips[indexStrip][indexLastLine].start.x << " " << vStrips[indexStrip][indexLastLine].start.y << endl;
cout << vStrips[indexStrip][indexLastLine].end.x << " " << vStrips[indexStrip][indexLastLine].end.y << endl;*/
}
}
}
}
}
fout << incedPoints << "\n";
//cout << SegmentsIntersect(Segment(0,60000, 60000,60000), Segment(60000,0, 60000, 60001)) << endl;
fin.close();
fout.close();
return 0;
}