Pagini recente » Cod sursa (job #2819800) | Cod sursa (job #2195085) | Cod sursa (job #1790704) | exemplu12 | Cod sursa (job #1396734)
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <utility>
#define x first
#define y second
using namespace std;
struct line
{
double a, b, c;
line()
{
a = b = c = 0;
}
line(pair<double, double> A, pair<double, double> 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<double, double> poly[kMax];
line l[kMax];
int getRandomNumber()
{
const int kMore = 60001;
int r = rand() + kMore;
return r;
}
bool areParallel(line a, line b)
{
return (a.a * b.b - 1LL * a.b * b.a == 0.0);
}
bool isOnSegment(double dx, double dy, pair<double, double> A, pair<double, double> B)
{
if (min(A.x, B.x) <= dx && dx <= max(A.x, B.x) && min(A.y, B.y) <= dy && dy <= max(A.y, B.y))
return true;
return false;
}
bool isInPolygon(pair<double, double> point)
{
int intersections = 0;
pair<double, double> rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
for (int i = 1; i <= n; ++i)
{
line ray = line(point, rayOrigin);
double det = ray.a * l[i].b - ray.b * l[i].a;
while (areParallel(ray, l[i]))
{
rayOrigin = make_pair(getRandomNumber(), getRandomNumber());
ray = line(point, rayOrigin);
det = ray.a * l[i].b - ray.b * l[i].a;
}
double solX = -(ray.c * l[i].b - l[i].c * ray.b) / det;
double solY = -(ray.a * l[i].c - 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)
{
double 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--)
{
double x, y;
fin >> x >> y;
if (isInPolygon(make_pair(x, y)))
++res;
}
fout << res << '\n';
return 0;
}