Cod sursa(job #2702709)

Utilizator retrogradLucian Bicsi retrograd Data 5 februarie 2021 16:03:14
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 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); }

const int MAXC = 2e9;

namespace std {
  bool operator<(const Point& a, const Point& b) {
    return make_pair(a.real(), a.imag()) < make_pair(b.real(), b.imag());
  }
};

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) {
    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], 1 + 2 * vert, i),
    evs.emplace_back(P[b], 0 + 2 * vert, i);
  }
  for (int i = 0; i < q; ++i)
    evs.emplace_back(Q[i], 4, i);
  // Solve.
  sort(evs.begin(), evs.end());
  auto cmp = [&](int i, int j) {
    auto [a, b] = E[i]; auto [p, q] = E[j];
    assert(a != b);
    return det(P[a] + P[a], P[b] + P[b], P[p] + P[q]) < 0;
  };
  set<int, decltype(cmp)> s(cmp);
  int vert = -1;
  vector<int> ans(q, -1);
  P.emplace_back(); E.emplace_back();
  for (auto [at, t, i] : evs) {
    if (t == 0) s.erase(i);
    if (t == 1) s.insert(i);
    if (t == 2) vert = -1;
    if (t == 3) vert = i;
    if (t == 4) {
      P[n] = Q[i]; E[m] = {n, n};
      if (vert != -1) ans[i] = vert;
      else {
        auto it = s.lower_bound(m);
        if (it != s.end()) ans[i] = *it;
      }
    }
  }
  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 i = 0, j = n - 1; i < n; j = i++) {
    E[i] = {j, i};
    area += cross(P[j], P[i]);
  }
  if (area < 0) reverse(P.begin(), P.end());
  auto sp = P; sort(sp.begin(), sp.end());
  m = remove_if(Q.begin(), Q.end(), [&](Point p) {
    return binary_search(sp.begin(), sp.end(), p);
  }) - Q.begin();
  int cnt = Q.size() - m;
  Q.resize(m);

  auto ans = Locate(P, E, Q);
  for (int i = 0; i < m; ++i) {
    if (ans[i] == -1) continue;
    auto [a, b] = E[ans[i]];
    cnt += (det(P[a], P[b], Q[i]) >= 0);
  }
  cout << cnt << endl;

  return 0;
}