Pagini recente » Cod sursa (job #2262761) | Cod sursa (job #566222) | Cod sursa (job #90021) | Cod sursa (job #1633695) | Cod sursa (job #2444101)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const double eps = 0.0000001;
const double Inf = 1000000000.;
double Abs(double a)
{
return a >= 0 ? a : -a;
}
struct Point{
double x, y;
bool operator == (const Point& p) const
{
return Abs(p.x - x) < eps && Abs(p.y - y) < eps;
}
};
struct Line{
double a, b, c;
};
double xmin{Inf}, xmax{-Inf};
struct Segment{
Point p1, p2;
double a, b, c;
Segment(Point p1, Point p2)
: p1(p1), p2(p2)
{
a = p1.y - p2.y;
b = p2.x - p1.x;
c = p1.x * p2.y - p2.x * p1.y;
}
int Intersect(Point p) const // 0 - nu intersecteaza, 1 - intersecteaza segmentul, 2 - se afla pe segment
{
Line other{0, 1, -p.y};
if (Abs(a * p.x + b * p.y + c) < eps)
{
if (min(p1.x, p2.x) <= p.x && p.x <= max(p1.x, p2.x)
&& min(p1.y, p2.y) <= p.y && p.y <= max(p1.y, p2.y))
return 2;
}
if (Abs(other.b * a - b * other.a) < eps)
return 0;
Point I{(b * other.c - other.b * c) / (other.b * a - b * other.a)
,(other.a * c - a * other.c) / (other.b * a - b * other.a)};
// =====Rules of intersection=====
if (p2.y > p1.y && I == p2)
return 0;
if (p2.y < p1.y && I == p1)
return 0;
if (a == 0)
return 0;
if (I.x < p.x)
return 0;
// ===============================
bool ok = (min(p1.x, p2.x) <= I.x && I.x <= max(p1.x, p2.x)
&& min(p1.y, p2.y) <= I.y && I.y <= max(p1.y, p2.y));
return ok;
}
};
int N, M;
vector<Point> p;
vector<Segment> s;
int cnt;
void ReadData();
void MakeSegments();
bool Check(Point p);
int main()
{
ReadData();
MakeSegments();
Point p;
for (int i = 1; i <= M; ++i)
{
fin >> p.x >> p.y;
cnt += Check(p);
}
fout << cnt << '\n';
fin.close();
fout.close();
return 0;
}
void ReadData()
{
fin >> N >> M;
p = vector<Point>(N);
for (int i = 0; i < N; ++i)
{
fin >> p[i].x >> p[i].y;
xmin = min(xmin, p[i].x);
xmax = max(xmax, p[i].x);
}
}
void MakeSegments()
{
for (int i = 0; i < N; ++i)
s.emplace_back(p[i], p[(i + 1) % N]);
}
bool Check(Point p)
{
int cnt{0}, r;
for (const Segment& segm : s)
{
r = segm.Intersect(p);
if (r == 2)
return true;
cnt += r;
}
return (cnt & 1);
}