Pagini recente » Cod sursa (job #1894851) | Cod sursa (job #2596521) | Cod sursa (job #2923052) | Cod sursa (job #2912932) | Cod sursa (job #1758650)
#include <bits/stdc++.h>
using namespace std;
const int kMaxC = 60005;
typedef pair<int, int> Point;
#define x first
#define y second
Point P[1005];
vector<int> Enter[kMaxC], Exit[kMaxC], Q[kMaxC];
vector<pair<int, int>> Verts[kMaxC];
int n;
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
void Debug(string);
struct LineSet {
struct cmp {
static int x;
static long double evaluate_line(int i) {
// Evaluate line i at coord x
// y(x) = y0 + (x - x0) * (dy / dx)
return P[i - 1].y + 1.0 * (x - P[i - 1].x) * (P[i].y - P[i - 1].y) / (P[i].x - P[i - 1].x);
}
bool operator()(const int &a, const int &b) const {
return evaluate_line(a) < evaluate_line(b);
}
};
typedef tree <
int, // Key Type
null_type, // Mapped type
cmp, // Compare functor
rb_tree_tag, // Tree tag: [rb_tree_tag|splay_tree_tag|ov_tree_tag]
tree_order_statistics_node_update // Update policy
> ordered_set;
ordered_set Set;
void ChangeX(int nw) {cmp::x = nw;}
void Insert(int i) {
Set.insert(i);
Debug("Inserted: " + to_string(i));
}
void Erase(int i) {
Set.erase(i);
Debug("Erased: " + to_string(i));
}
bool Solve(int y) {
P[n + 1] = Point(cmp::x, y);
P[n + 2] = Point(cmp::x + 1, y);
auto it = Set.lower_bound(n + 2);
if(it == Set.end()) return 0;
Debug("Iterator has value: " + to_string(*it));
if(cmp::evaluate_line(*it) == y) return true;
Debug(to_string(Set.order_of_key(n + 2)));
return (Set.order_of_key(n + 2) % 2);
}
};
int LineSet::cmp::x = 0;
void Debug(string message) {
cerr << "[" << LineSet::cmp::x << "] " << message << '\n';
}
LineSet Set;
int Solve() {
int ans = 0;
for(int cur_x = 0; cur_x <= 60000; ++cur_x) {
auto &enter = Enter[cur_x];
auto &exit = Exit[cur_x];
auto &verts = Verts[cur_x];
Set.ChangeX(cur_x);
for(int i : enter) Set.Insert(i);
sort(verts.begin(), verts.end());
for(auto cur_y : Q[cur_x]) {
// Check in verts
auto it = lower_bound(verts.begin(), verts.end(), make_pair(cur_y, 100000));
if(it != begin(verts)) {
--it;
assert(it->first <= cur_y);
if(it->second >= cur_y) {
ans += 1;
Debug("Got(from vertical): " + to_string(cur_y));
continue;
}
}
if(Set.Solve(cur_y)) {
ans += 1;
Debug("Got(from oblique): " + to_string(cur_y));
}
}
for(auto i : exit) Set.Erase(i);
}
return ans;
}
int main() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
int m;
cin >> n >> m;
for(int i = 1; i <= n; ++i)
cin >> P[i].x >> P[i].y;
P[0] = P[n];
for(int i = 1; i <= n; ++i) {
int x1 = P[i - 1].x;
int x2 = P[i].x;
if(x1 == x2) {
int y1 = P[i - 1].y;
int y2 = P[i].y;
if(y1 < y2) Verts[x1].emplace_back(y1, y2 - 1);
else Verts[x1].emplace_back(y2 + 1, y1);
continue;
}
if(x1 < x2) --x2;
else {
swap(x1, x2);
++x1;
}
Enter[x1].push_back(i);
Exit[x2].push_back(i);
}
for(int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
Q[x].push_back(y);
}
cout << Solve() << endl;
return 0;
}