Pagini recente » Cod sursa (job #2454674) | Cod sursa (job #377904) | Cod sursa (job #909842) | Cod sursa (job #599279) | Cod sursa (job #2641850)
#define MAX_N 800
#define MAX_M 60000
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct point
{
int x, y;
};
int n, m;
point P[MAX_N + 1], C[MAX_M + 1];
point corner = { 60001, 60001 };
int Sign(const point& p1, const point& p2, const point& p3);
bool IsInside(const point& p);
//void CoutPoint(const point& p);
int main()
{
fin >> n >> m;
for (int i = 1; i <= n; ++i)
{
fin >> P[i].x >> P[i].y;
if (corner.x > P[i].x)
{
corner = P[i];
}
else
{
if (corner.x == P[i].x)
{
if (corner.y > P[i].y)
{
corner = P[i];
}
}
}
}
int r = 0;
for (int i = 1; i <= m; ++i)
{
fin >> C[i].x >> C[i].y;
bool inside = IsInside(C[i]);
if (inside)
{
++r;
}
/*
cout << "Is inside: " << inside << "; " << "{ " << C[i].x << ", " << C[i].y << " }\n";
cin.get();
*/
}
fout << r;
fin.close();
fout.close();
return 0;
}
/*
void CoutPoint(const point& p)
{
cout << "{ " << p.x << ", " << p.y << " }";
}
*/
int Sign(const point& p1, const point& p2, const point& p3)
{
return ((p1.x - p3.x) * (p2.y - p3.y)) - ((p2.x - p3.x) * (p1.y - p3.y));
}
bool IsInside(const point& p)
{
int intersectionCount = 0;
for (int i = 1; i <= n; ++i)
{
point p1, p2;
if (i < n)
{
p1 = P[i];
p2 = P[i + 1];
}
else
{
p1 = P[n];
p2 = P[1];
}
const int sngp1 = Sign(corner, p, p1);
const int sngp2 = Sign(corner, p, p2);
const bool psngp1 = sngp1 >= 0;
const bool psngp2 = sngp2 >= 0;
if ((sngp1 == 0) && (sngp2 == 0))
{
//cout << "sngp1 = sngp2 = 0\n";
if ((p1.x == 0) && (p2.x == 0))
{
if ((min(p1.y, p2.y) <= p.y) && (p.y <= max(p1.y, p2.y)))
{
/*
cout << "x1 = x2 = 0;\n";
CoutPoint(corner);
cout << ' ';
CoutPoint(p);
cout << ' ';
CoutPoint(p1);
cout << ' ';
CoutPoint(p2);
cout << '\n';
cin.get();
*/
return true;
}
}
else
{
if ((min(p1.x, p2.x) <= p.x) && (p.x <= max(p1.x, p2.x)))
{
/*
CoutPoint(corner);
cout << ' ';
CoutPoint(p);
cout << ' ';
CoutPoint(p1);
cout << ' ';
CoutPoint(p2);
cout << '\n';
cin.get();
*/
return true;
}
}
}
if (psngp1 == psngp2)
{
continue;
}
point a1 = p1;
point a2 = p2;
if (sngp2 < 0)
{
swap(a1, a2);
}
if (Sign(a1, a2, p) >= 0)
{
++intersectionCount;
}
}
/*
cout << "Intersection count: " << intersectionCount << "; " << "{ " << p.x << ", " << p.y << " }\n";
cin.get();
*/
return intersectionCount & 1;
}