Cod sursa(job #2516860)

Utilizator rapunzelMihnea Andreescu rapunzel Data 2 ianuarie 2020 15:06:36
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Lista lui wefgef Marime 1.43 kb
/// Crave your name into those shining stars
#include <cstdio>
#include <iostream>

using namespace std;

struct point {
  int x;
  int y;
};

long long ar(point a, point b) {
  return (long long) (a.x - b.x) * (a.y + b.y);
}

long long ar(point a, point b, point c) {
  return ar(a, b) + ar(b, c) + ar(c, a);
}

bool coli(point a, point b, point c) {
  return (ar(a, b, c) == 0);
}

bool in_box(point a, point b, point p) {
  return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool on_segment(point a, point b, point p) {
  return (coli(a, b, p) && in_box(a, b, p));
}

bool under_segment(point a, point b, point p) {
  return min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && ar(a, b, p) > 0;
}

const int N = 800 + 7;
int n;
int q;
point a[N];

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

  scanf("%d %d", &n, &q);
  for (int i = 0; i < n; i++) scanf("%d %d", &a[i].x, &a[i].y);
  a[n] = a[0];
  int sol = 0;
  for (int i = 0; i < q; i++) {
    point p;
    scanf("%d %d", &p.x, &p.y);
    bool on_side = 0;
    int ok = 0;
    for (int i = 0; i < n; i++) {
      if (on_segment(a[i], a[i + 1], p)) {
        on_side = 1;
        break;
      }
      if (under_segment(a[i], a[i + 1], p)) {
        ok ^= 1;
      }
    }
    if (on_side || ok) {
      sol++;
    }
  }
  printf("%d\n", sol);

}