Cod sursa(job #2334701)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 2 februarie 2019 21:45:54
Problema Poligon Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#include <fstream>
#include <cmath>

using namespace std;

ifstream cin("poligon.in");
ofstream cout("poligon.out");

typedef long double ld;

struct point {
  int x;
  int y;
};

ld dist(point a, point b) {
  ld dx = a.x - b.x;
  ld dy = a.y - b.y;
  ld s = dx * dx + dy * dy;
  return sqrt(s);
}

bool coliniar(point a, point b, point c) {
  ld d1 = dist(a, b);
  ld d2 = dist(a, c);
  ld d3 = dist(b, c);
  ld p = (d1 + d2 + d3) * 0.5;
  if (p == 0 || p == d1 || p == d2 || p == d3) {
    return 1;
  } else {
    return 0;
  }
}

bool onSegment(point p, point q, point r) {
    return (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) && q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y));
}

int orientation(point p, point q, point r) {
    int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;
    return (val > 0)? 1: 2;
}

bool doIntersect(point p1, point q1, point p2, point q2)
{
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
    if (o1 != o2 && o3 != o4) return 1;
    if (o1 == 0 && onSegment(p1, p2, q1)) return 1;
    if (o2 == 0 && onSegment(p1, q2, q1)) return 1;
    if (o3 == 0 && onSegment(p2, p1, q2)) return 1;
    if (o4 == 0 && onSegment(p2, q1, q2)) return 1;
    return 0;
}

int n, m;
point a[800 + 7];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  a[n + 1] = a[1];
  int res = 0;
  for (int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    bool ok = 0;
    int cnt = 0;
    for (int j = 1; j <= n && (ok == 0); j++) {
      if (onSegment(a[j], {x, y}, a[j + 1])) {
        ok = 1;
      }
      if (doIntersect({x, y}, {x, 60000 + 7}, a[j], a[j + 1])) {
        cnt++;
      }
    }
    if (ok || cnt % 2 == 1) {
      res++;
    }
  }
  cout << res << "\n";
  return 0;
}