Cod sursa(job #2171385)

Utilizator cella.florescuCella Florescu cella.florescu Data 15 martie 2018 12:10:15
Problema Poligon Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

const int MAXN = 8e2;
const int MAXCOORD = 6e4 + 10;
const int LGP2 = 10;

struct Point {
  int x, y;
  bool operator == (const Point &other) const {
    return x == other.x && y == other.y;
  }
  bool operator < (const Point& other) const {
    if (x == other.x)
      return y < other.y;
    return x < other.x;
  }
} pts[MAXN + 1];

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;
}

struct Segment {
  Point A, B;
  bool operator < (const Segment& other) const {
    if (A == other.A && B == other.B)
      return 0;
    return det(A, B, other.A) >= 0LL && det(A, B, other.B) >= 0LL;
  }
} v[MAXN + 1];

struct VerticalShit {
  int x, y1, y2;
  bool operator < (const VerticalShit& other) const {
    if (x == other.x)
      return y2 < other.y1;
    return x < other.x;
  }
};

vector <VerticalShit> vert;

struct Region {
  int lft, rgh;
  vector <Segment> sg;
} reg[MAXN + 3];

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 || pts[pos + step] == P))
      pos += step;
  return (pts[pos] == P);
}

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

int main()
{
    int n, m;
    ifstream fin("poligon.in");
    fin >> n >> m;
    for (int i = 0; i < n; ++i)
      fin >> pts[i].x >> pts[i].y;
    pts[n] = pts[0];
    for (int i = 0; i < n; ++i) {
      v[i] = {pts[i], pts[i + 1]};
      if (v[i].B < v[i].A)
        swap(v[i].A, v[i].B);
      if (v[i].A.x == v[i].B.x)
        vert.push_back({v[i].A.x, v[i].A.y, v[i].B.y});
    }
    v[n] = {{-MAXCOORD, MAXCOORD}, {MAXCOORD, MAXCOORD}};
    sort(vert.begin(), vert.end());
    sort(pts, pts + n);
    int num_reg = 0;
    reg[num_reg].lft = -MAXCOORD;
    reg[num_reg++].rgh = pts[0].x;
    for (int i = 0; i < n - 1; ++i)
      if (pts[i].x < pts[i + 1].x) {
        reg[num_reg].lft = pts[i].x;
        reg[num_reg].rgh = pts[i + 1].x;
        for (int j = 0; j <= n; ++j)
          if (v[j].A.x <= reg[num_reg].lft && reg[num_reg].rgh <= v[j].B.x)
            reg[num_reg].sg.push_back(v[j]);
        sort(reg[num_reg].sg.begin(), reg[num_reg].sg.end());
        ++num_reg;
      }
    reg[num_reg].lft = pts[n - 1].x;
    reg[num_reg++].rgh = MAXCOORD;
    int ans = 0;
    for (int i = 0; i < m; ++i) {
      int x, y;
      fin >> x >> y;
      int wh_reg = 0;
      for (int step = 1 << LGP2; step > 0; step >>= 1)
        if (wh_reg + step < num_reg && reg[wh_reg + step].lft <= x)
          wh_reg += step;
      int num = -1;
      for (int step = 1 << LGP2; step > 0; step >>= 1)
        if (num + step < (int) reg[wh_reg].sg.size() && det(reg[wh_reg].sg[num + step].A, reg[wh_reg].sg[num + step].B, {x, y}) > 0)
          num += step;
      ++num;
      if (on_vertical_shit({x, y}))
        ++ans;
      else if (input_point({x, y}, n))
        ++ans;
      else if (reg[wh_reg].sg.size())
        ans += (det({x, y}, reg[wh_reg].sg[num].B, reg[wh_reg].sg[num].A) == 0LL || num % 2);
    }
    fin.close();
    ofstream fout("poligon.out");
    fout << ans;
    fout.close();
    return 0;
}