Cod sursa(job #2702742)

Utilizator retrogradLucian Bicsi retrograd Data 5 februarie 2021 17:56:20
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], 1 + 2 * vert, i),
    evs.emplace_back(P[b], 0 + 2 * vert, i);
  }
  for (int i = 0; i < n; ++i) evs.emplace_back(P[i], 4, i);
  for (int i = 0; i < q; ++i) evs.emplace_back(Q[i], 5, 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) s.insert(i);
    if (t == 2) vert = -1;
    if (t == 3) vert = i;
    if (t == 4) last = i;
    if (t == 5) {
      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;
      }
    }
    
    // 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;
}