Pagini recente » Cod sursa (job #1691583) | Cod sursa (job #3272235) | Cod sursa (job #2399583) | Cod sursa (job #2594836) | Cod sursa (job #1396733)
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <utility>
#define x first
#define y second
using namespace std;
struct line
{
long long a, b, c;
line()
{
a = b = c = 0;
}
line(pair<int, int> A, pair<int, int> B)
{
a = B.y - A.y;
b = A.x - B.x;
c = 1LL * (-a) * A.x - 1LL * b * A.y;
}
};
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const int kMax = 60010;
int n, m;
pair<int, int> poly[kMax];
line l[kMax];
int getRandomNumber()
{
const int kMore = 60001;
int r = rand() + kMore;
return r;
}
bool areParallel(line a, line b)
{
return (1LL * a.a * b.b - 1LL * a.b * b.a == 0);
}
bool isOnSegment(double dx, double dy, pair<int, int> A, pair<int, int> B)
{
double Ax = A.x, Ay = A.y, Bx = B.x, By = B.y;
if (min(Ax, Bx) <= dx && dx <= max(Ax, Bx) && min(Ay, By) <= dy && dy <= max(Ay, By))
return true;
return false;
}
bool isInPolygon(pair<int, int> point)
{
int intersections = 0;
pair<int, int> rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
for (int i = 1; i <= n; ++i)
{
line ray = line(point, rayOrigin);
double det = 1.0 * ray.a * l[i].b - 1.0 * ray.b * l[i].a;
while (areParallel(ray, l[i]))
{
rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
ray = line(point, rayOrigin);
det = 1.0 * ray.a * l[i].b - 1.0 * ray.b * l[i].a;
}
double solX = -(1.0 * ray.c * l[i].b - 1.0 * l[i].c * ray.b) / det;
double solY = -(1.0 * ray.a * l[i].c - 1.0 * l[i].a * ray.c) / det;
if (isOnSegment(solX, solY, poly[i], poly[i + 1]) && isOnSegment(solX, solY, point, rayOrigin))
++intersections;
}
return (intersections % 2);
}
int main()
{
srand(time(NULL));
fin >> n >> m;
for (int i = 1; i <= n; ++i)
{
int x, y; fin >> x >> y;
poly[i] = make_pair(x, y);
}
poly[n + 1] = poly[1];
for (int i = 1; i <= n; ++i)
l[i] = line(poly[i], poly[i + 1]);
int res = 0;
while (m--)
{
int x, y;
fin >> x >> y;
if (isInPolygon(make_pair(x, y)))
++res;
}
fout << res << '\n';
return 0;
}