Nu aveti permisiuni pentru a descarca fisierul grader_test6.ok
Cod sursa(job #2702743)
Utilizator | Data | 5 februarie 2021 18:00:07 | |
---|---|---|---|
Problema | Poligon | Scor | 60 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 3.24 kb |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Point = complex<ll>;
ll cross(Point a, Point b) { return a.real() * b.imag() - a.imag() * b.real(); }
ll dot(Point a, Point b) { return a.real() * b.real() + a.imag() * b.imag(); }
ll det(Point a, Point b, Point c) { return cross(b - a, c - a); }
namespace std {
bool operator<(const Point& a, const Point& b) {
return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
}
};
int sgn(ll d) { return d == 0 ? 0 : d > 0 ? 1 : -1; }
vector<int> Locate(vector<Point> P, vector<pair<int, int>> E, vector<Point> Q) {
int n = P.size(), m = E.size(), q = Q.size();
// Make sweepline events.
vector<tuple<Point, int, int>> evs;
for (int i = 0; i < m; ++i) {
int &a = E[i].first, &b = E[i].second;
// auto [a, b] = E[i];
if (P[b] < P[a]) swap(a, b);
int vert = P[a].real() == P[b].real();
evs.emplace_back(P[a], vert + 4, i),
evs.emplace_back(P[b], vert + 0, i);
}
for (int i = 0; i < n; ++i) evs.emplace_back(P[i], 2, i);
for (int i = 0; i < q; ++i) evs.emplace_back(Q[i], 3, i);
// Solve.
sort(evs.begin(), evs.end());
auto cmp = [&](int i, int j) {
int a, b, p, q; tie(a, b) = E[i]; tie(p, q) = E[j];
// auto [a, b] = E[i]; auto [p, q] = E[j];
return det(P[a] + P[a], P[b] + P[b], P[p] + P[q]) >
det(P[p] + P[p], P[q] + P[q], P[a] + P[b]);
};
set<int, decltype(cmp)> s(cmp);
int vert = -1, last = -1;
vector<int> ans(q, -1);
P.emplace_back(); E.emplace_back();
// for (int i = 0; i < m; ++i) cerr << "[" << P[E[i].first] << " " << P[E[i].second] << "] ";
// cerr << endl;
// for (int i = 0; i < m; ++i) {
// for (int j = 0; j < m; ++j)
// cerr << cmp(i, j);
// cerr << endl;
// }
for (auto itr : evs) {
Point at; int t, i; tie(at, t, i) = itr;
if (t == 0) s.erase(i);
if (t == 1) vert = -1;
if (t == 2) last = i;
if (t == 3) {
if (last != -1 && P[last] == Q[i]) ans[i] = -2;
else if (vert != -1) ans[i] = vert;
else {
P[n] = Q[i]; E[m] = {n, n};
auto it = s.lower_bound(m);
if (it != s.end()) ans[i] = *it;
}
}
if (t == 4) s.insert(i);
if (t == 5) vert = i;
// cerr << "Event: " << at << " " << t << " " << i << endl;
// cerr << " vert: " << vert << endl;
// cerr << " set: ";
// for (auto i : s) cerr << "[" << P[E[i].first] << " " << P[E[i].second] << "] ";
// cerr << endl;
}
return ans;
}
int main() {
ifstream cin("poligon.in");
ofstream cout("poligon.out");
int n, m; cin >> n >> m;
auto read = [&]() {
int x, y; cin >> x >> y;
return Point{x, y};
};
vector<Point> P(n), Q(m);
vector<pair<int, int>> E(n);
for (int i = 0; i < n; ++i) P[i] = read();
for (int i = 0; i < m; ++i) Q[i] = read();
ll area = 0;
for (int j = n - 1, i = 0; i < n; j = i++) {
area += cross(P[j], P[i]);
E[i] = {j, i};
}
if (area < 0) reverse(P.begin(), P.end());
auto ans = Locate(P, E, Q);
int cnt = 0;
for (int i = 0; i < m; ++i) {
if (ans[i] == -1) continue;
if (ans[i] == -2) { cnt += 1; continue; }
int a, b; tie(a, b) = E[ans[i]];
// auto [a, b] = E[ans[i]];
if (det(P[a], P[b], Q[i]) >= 0) cnt += 1;
}
cout << cnt << endl;
return 0;
}