Cod sursa(job #589210)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 11 mai 2011 15:30:30
Problema Poligon Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct pct {
  int x, y;
};

const int N = 850;

int n, m, vx[N];

pair <pct, pct> v[N];

vector <pair <double, int> > strip[N];

vector <pair <int, int> > line[N];

void read() {
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= n; ++ i) {
    scanf("%d%d", &v[i].first.x, &v[i].first.y);

    vx[++ vx[0]] = v[i].first.x;
  }
}

inline bool comp(pct A, pct B) {
  if (A.x < B.x)
    return true;

  if (A.x > B.x)
    return false;

  return A.y < B.y;
}

void init() {
  for (int i = 1; i < n; ++ i)
    v[i].second = v[i + 1].first;

  v[n].second = v[1].first;

  for (int i = 1; i <= n; ++ i)
    if (! comp(v[i].first, v[i].second))
      swap(v[i].first, v[i].second);
}

inline double inters(pair <pct, pct> a, int x) {
  double m = (double)(a.first.y - a.second.y) / (a.first.x - a.second.x);

  if (m == 0)
    return a.first.y;

  return (double)m *((double)x - a.first.x) + (double)a.first.y;
}

void linie(int poz) {
  for (int i = 1; i <= n; ++ i)
    if (v[i].first.x == vx[poz] && vx[poz] == v[i].second.x)
        line[poz].push_back(make_pair(v[i].first.y, v[i].second.y));
}

void fasie(int poz) {
  if (poz == vx[0])
    return;

  for (int i = 1; i <= n; ++ i)
    if (v[i].first.x <= vx[poz] && vx[poz + 1] <= v[i].second.x)
      strip[poz].push_back(make_pair(inters(v[i], (vx[poz] + vx[poz + 1]) / 2), i));
}

void shiftare_stanga(int poz, int v[N]) {
  for (int i = poz; i <= v[0]; ++ i)
    v[i] = v[i + 1];
}

void scoate_duplicate(int v[N]) {
  for (int i = 2; i <= v[0]; ++ i)
    if (v[i] == v[i - 1]) {
      shiftare_stanga(i, v);
      -- v[0];
      -- i;
    }
}

void preproc() {
  sort(vx + 1, vx + vx[0] + 1);

  scoate_duplicate(vx);

  for (int i = 1; i <= vx[0]; ++ i) {
    linie(i);
    fasie(i);
  }

  for (int i = 1; i <= vx[0]; ++ i) {
    sort(line[i].begin(), line[i].end());
    sort(strip[i].begin(), strip[i].end());
  }
}

int cautb(int x) {
  int pas = 1 << 10, i = 0;

  for (i = 0; pas; pas >>= 1)
    if (i + pas <= vx[0] && vx[i + pas] <= x)
      i += pas;

  return i;
}

inline double unghi(int x1, int y1, int x2, int y2) {
    double a = asin((double)(y2 - y1) / sqrt((double)(x2- x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))) / M_PI * 180;

    if (y2 >= y1)
        return a;

    return (double)360 + a;
}

inline bool pct_deasupra(int i, int x3, int y3) {
  double u1 = unghi(v[i].first.x, v[i].first.y, v[i].second.x, v[i].second.y);
  double u2 = unghi(v[i].first.x, v[i].first.y, x3, y3);

  if (u1 <= 90 && u2 <= 90) {
    if (u1 <= u2)
      return true;
    return false;
  }

  if (u1 >= 270 && u2 >= 270) {
    if (u1 <= u2)
      return true;
    return false;
  }

  if (u1 <= 90 && u2 >= 270)
    return false;

  if (u1 >= 270 && u2 <= 90)
    return true;
}

bool verif_fasie(int x, int y, int poz) {
  int i = 0, pas = 1 << 10;

  for (i = - 1; pas; pas >>= 1)
    if (i + pas < strip[poz].size() && pct_deasupra(strip[poz][i + pas].second, x, y))
      i += pas;

  if ((strip[poz].size() - i - 1) % 2 == 1)
    return 1;

  return 0;
}

bool verif_linie(int x, int y, int poz) {
  int i = 0, pas = 1 << 10;

  for (i = - 1; pas; pas >>= 1)
    if (i + pas < line[poz].size() && line[poz][i + pas].first <= y)
      i += pas;

  if (i == - 1 || line[poz][i].second < y)
    return 0;

  return 1;
}

void solve() {
  int x, y, nrp = 0;

  for (int i = 1; i <= m; ++ i) {
    scanf("%d%d", &x, &y);

    if (x < vx[1] || x > vx[vx[0]])
      continue;

    int poz = cautb(x);

    if (verif_fasie(x, y, poz) || (x == vx[poz] && verif_linie(x, y, poz)))
      ++ nrp;
  }

  printf("%d\n", nrp);
}

int main() {
  freopen("poligon.in", "r", stdin);
  freopen("poligon.out", "w", stdout);

  read();

  init();

  preproc();

  solve();

  return 0;
}