Cod sursa(job #2204929)

Utilizator cella.florescuCella Florescu cella.florescu Data 17 mai 2018 11:31:48
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.45 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#define x first
#define y second

using namespace std;

const int MAXN = 8e2;
const int MAXCOORD = 6e4 + 10;
const int LGP2 = 10;
typedef pair <int, int> Point;
typedef pair <Point, Point> Segment;

Point pts[MAXN + 1];
vector <int> vert[MAXCOORD], xcoord;
vector <int> reg[MAXN + 3];
double aux;
int cln;

inline long long det(Point A, Point B, Point C) {
  return 1LL * A.x * B.y + 1LL * B.x * C.y + 1LL * C.x * A.y - 1LL * A.y * B.x - 1LL * B.y * C.x - 1LL * C.y * A.x;
}


inline double sg_cmp(Point A, Point B, double x) {
  return A.y + (B.y - A.y) * (aux - A.x) / (1.0 * B.x - A.x);
}

bool cmp(int A, int B) {
  return sg_cmp(pts[A], pts[A + 1], aux) < sg_cmp(pts[B], pts[B + 1], aux);
}

inline int bin_src_cmp(int ind, Point P) {
  long long tmp = det(min(pts[ind], pts[ind + 1]), max(pts[ind], pts[ind + 1]), P);
  if (tmp == 0)
    cln = 1;
  return (tmp >= 0);
}

inline int input_point(Point P, int n) {
  int pos = 0;
  for (int step = 1 << LGP2; step > 0; step >>= 1)
    if (pos + step < n && pts[pos + step] <= P)
      pos += step;
  return (pts[pos] == P);
}

inline int on_vertical_shit(Point P) {
  int pos = -1;
  for (int step = 1 << LGP2; step > 0; step >>= 1)
    if (pos + step < (int) vert[P.x].size() && vert[P.x][pos + step] <= P.y)
      pos += step;
  ++pos;
  return ((pos & 1) || (pos > 0 && vert[P.x][pos - 1] == P.y));
}

inline int check_reg(Point P, int region) {
  if (region <= 0 || P.x > xcoord[region + 1])
    return 0;
  cln = 0;
  int pos = -1;
  for (int step = 1 << LGP2; step > 0; step >>= 1)
    if (pos + step < (int) reg[region].size() && bin_src_cmp(reg[region][pos + step], P))
      pos += step;
  ++pos;
  return (cln || (pos & 1));
}

int main()
{
    int n, m;
    ifstream fin("poligon.in");
    fin >> n >> m;
    xcoord.resize(n + 2);
    for (int i = 0; i < n; ++i) {
      fin >> pts[i].x >> pts[i].y;
      xcoord[i + 1] = pts[i].x;
    }
    pts[n] = pts[0];
    xcoord[0] = -MAXCOORD;
    xcoord[n + 1] = MAXCOORD;
    sort(xcoord.begin(), xcoord.end());
    auto last = unique(xcoord.begin(), xcoord.end());
    xcoord.erase(last, xcoord.end());
    for (int i = 0; i < n; ++i)
      if (pts[i].x == pts[i + 1].x) {
        vert[pts[i].x].push_back(pts[i].y);
        vert[pts[i].x].push_back(pts[i + 1].y);
      }
    for (int i = 1; i < (int) xcoord.size() - 1; ++i)
      sort(vert[xcoord[i]].begin(), vert[xcoord[i]].end());
    for (int i = 0; i < (int) xcoord.size() - 1; ++i) {
      for (int j = 0; j < n; ++j)
        if ((pts[j].x <= xcoord[i] && xcoord[i + 1] <= pts[j + 1].x) || (pts[j + 1].x <= xcoord[i] && xcoord[i + 1] <= pts[j].x))
          reg[i].push_back(j);
      aux = (xcoord[i] + xcoord[i + 1]) / 2.0;
      sort(reg[i].begin(), reg[i].end(), cmp);
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      int x, y;
      fin >> x >> y;
      if (on_vertical_shit({x, y}) || input_point({x, y}, n))
        ++ans;
      else if (xcoord[1] <= x && x <= xcoord[(int) xcoord.size() - 2]){
        int r = 0;
        for (int step = 1 << LGP2; step > 0; step >>= 1)
          if (step + r < (int) xcoord.size() && xcoord[step + r] <= x)
            r += step;
        ans += (check_reg({x, y}, r - 1) || check_reg({x, y}, r));
      }
    }
    fin.close();
    ofstream fout("poligon.out");
    fout << ans;
    fout.close();
    return 0;
}