Pagini recente » Cod sursa (job #24087) | Cod sursa (job #2632813) | Cod sursa (job #1711298) | Cod sursa (job #2227063) | Cod sursa (job #2444340)
#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 int Inf = 0x3f3f3f3f;
const double Infd = 1e10;
double Abs(double a)
{
return a >= 0 ? a : -a;
}
struct Point{
int x, y;
bool operator < (const Point& p) const
{
return x < p.x;
}
bool operator == (const Point& p) const
{
return Abs(p.x - x) < eps && Abs(p.y - y) < eps;
}
};
struct Line{
int a, b, c;
};
int xmin{Inf}, xmax{-Inf};
struct Segment{
Point p1, p2;
int 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;
}
double GetY(int x) const
{
if (b == 0)
return -Infd;
return 1.*(-c - a * x) / b;
}
};
struct Compare{
static int x1, x2;
static bool Cmp(const Segment& s1, const Segment& s2)
{
return s1.GetY((x1 + x2) / 2) < s2.GetY((x1 + x2) / 2);
}
};
int Compare::x1 = 0;
int Compare::x2 = 0;
struct Strip{
int x1, x2;
vector<Segment> sgm;
Strip(int x1, int x2, const vector<Segment>& potentialSegm)
: x1{x1}, x2{x2}
{
for (const Segment& s : potentialSegm)
{
if ((min(s.p1.x, s.p2.x) < x2 && max(s.p1.x, s.p2.x) > x1) || s.b == 0)
sgm.push_back(s);
}
Compare::x1 = x1;
Compare::x2 = x2;
sort(sgm.begin(), sgm.end(), Compare::Cmp);
}
bool Intersect(Point p)
{
int lo{0}, hi{static_cast<int>(sgm.size()) - 1}, mid, res{static_cast<int>(sgm.size())};
while (lo <= hi && sgm[lo].b == 0)
{
if (Abs((1. * -sgm[lo].c) / sgm[lo].a - p.x) < eps
&& min(sgm[lo].p1.y, sgm[lo].p2.y) <= p.y && p.y <= max(sgm[lo].p1.y, sgm[lo].p2.y))
return true;
++lo;
}
while (lo <= hi)
{
mid = (lo + hi) / 2;
if (sgm[mid].GetY(p.x) >= p.y)
res = mid, hi = mid - 1;
else
lo = mid + 1;
}
// cout << (static_cast<int>(sgm.size()) - res) << '\n';
return ((static_cast<int>(sgm.size()) - res) & 1);
}
void Write()
{
cout << "Segmentul " << x1 << " - " << x2 << " : ";
for (const Segment& s : sgm)
cout << "( " << s.p1.x << ' ' << s.p1.y << "; " << s.p2.x << ' ' << s.p2.y << " );";
cout << '\n';
}
};
int N, M;
vector<Point> p;
vector<Segment> s;
vector<Strip> st;
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';
cout << 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]);
sort(p.begin(), p.end());
vector<int> X;
for (const Point& P : p)
if (X.empty() || X.back() != P.x)
X.push_back(P.x);
for (size_t i = 0; i + 1 < X.size(); ++i)
{
st.emplace_back(X[i], X[i + 1], s);
// st.back().Write();
}
}
bool Check(Point p)
{
if (p.x < xmin || p.x > xmax)
return false;
int lo{0}, hi{static_cast<int>(st.size()) - 1}, mid, res;
while (lo <= hi)
{
mid = (lo + hi) / 2;
if (st[mid].x1 <= p.x)
res = mid, lo = mid + 1;
else
hi = mid - 1;
}
return st[res].Intersect(p);
}