Pagini recente » Cod sursa (job #1756564) | Cod sursa (job #791840) | Cod sursa (job #638532) | Cod sursa (job #1241749) | Cod sursa (job #1808751)
#include <bits/stdc++.h>
using namespace std;
#define double long double
typedef complex<double> Point;
const double kRotAng = 0;// 441.3128;
const double kEps = 1e-9;
Point Rotate(Point p) {
return Point(
p.real() * 3.1241412 + p.imag() * 3.12124124,
p.real() * 1.1281251 + p.imag() * 3.11421281
);
}
double det(Point a, Point b, Point c) {
return (conj(b - a) * (c - a)).imag();
}
int main() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<Point> P(n);
for(int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
P[i] = Rotate(Point(a, b));
}
P.push_back(P.front());
vector<pair<Point, Point>> Edges;
for(int i = 1; i <= n; ++i) {
Edges.emplace_back(P[i - 1], P[i]);
}
for(auto &e : Edges) {
if(e.first.real() > e.second.real() + kEps)
swap(e.first, e.second);
}
sort(Edges.begin(), Edges.end(), [](pair<Point, Point> a, pair<Point, Point> b) {
if(norm(a.first - b.first) < kEps)
return a.second.imag() < b.second.imag();
return a.first.imag() < b.first.imag();
});
vector<pair<double, int>> Upd;
vector<pair<Point, int>> Qry(m);
for(int ei = 0; ei < Edges.size(); ++ei) {
auto e = Edges[ei];
Upd.emplace_back(e.first.real() - kEps, ei + 1);
Upd.emplace_back(e.second.real() + kEps, -(ei + 1));
}
int ans = 0;
for(int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
Qry[i] = {Rotate(Point(a, b)), i};
}
sort(Qry.begin(), Qry.end(), [](pair<Point, int> a, pair<Point, int> b) {
return a.first.real() + kEps < b.first.real();
});
sort(Upd.begin(), Upd.end());
vector<int> Active;
auto it = Upd.begin();
for(auto &q : Qry) {
while(it != Upd.end() && it->first < q.first.real()) {
if(it->second < 0) Active.erase(lower_bound(Active.begin(), Active.end(), -(it->second)));
else Active.insert(lower_bound(Active.begin(), Active.end(), it->second), it->second);
++it;
}
/*for(auto p : Edges) {
cerr << "<" << p.first << " " << p.second << "> ";
}
cerr << endl;*/
auto it = partition_point(Active.begin(), Active.end(), [&](int x) {
return det(Edges[x - 1].first, Edges[x - 1].second, q.first) > kEps;
});
if(it != Active.end() && abs(det(Edges[*it - 1].first, Edges[*it - 1].second, q.first)) < kEps) {
// cerr << "Point: " << q.first << " on boundary\n";
ans += 1;
} else if((it - Active.begin()) % 2) {
// cerr << "Point: " << q.first << " on interior\n";
ans += 1;
} else {
// cerr << "Point: " << q.first << " on exterior\n";
}
}
cout << ans << endl;
return 0;
}