Cod sursa(job #2500122)

Utilizator MiricaMateiMirica Matei MiricaMatei Data 27 noiembrie 2019 11:45:30
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda guritza Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

struct Punct {
  int x, y;

  bool operator == (const Punct& other) const {
    if (x == other.x && y == other.y)
      return 1;
    return 0;
  }
  bool operator != (const Punct& other) const {
    if (x == other.x && y == other.y)
      return 0;
    return 1;
  }
}v[805], a[60005];

bool sgn(Punct a, Punct b, Punct c) {
  long long s = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
  if (s < 0)
    return 1;
  else if (s > 0)
    return 0;
  return 2;
}

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

  int ans = 0;
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i)
    scanf("%d%d", &v[i].x, &v[i].y);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d", &a[i].x, &a[i].y);
    int k = 0, ok = 0, x = 0;
    for (int j = 1; j <= n; ++j) {
      int m1 = j % n + 1;
      if (a[i] == v[j]) {
        ok = 1;
        break;
      }
      if (a[i] != v[m1] && min(v[j].x, v[m1].x) <= a[i].x && a[i].x <= max(v[j].x, v[m1].x)) {
        int c = sgn(v[j], v[m1], a[i]);
        x++;
        k+=c;
        if (c == 2) {
          ok = 1;
          break;
        }
      }
    }
    if (ok || k == 0 || (k == x))
      ans++;
  }
  printf("%d\n", ans);

  return 0;
}