Cod sursa(job #1716903)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 13 iunie 2016 22:11:44
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int N_MAX = 805;

class Point {
  public:
    double x;
    double y;
    
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
};

class Segment {
  public:
    Point a;
    Point b;
    
    Segment() {}
    Segment(Point _a, Point _b) : a(_a), b(_b) {}
};

int n, m;
Point p[N_MAX];
vector<int> X;
vector<Segment> Z[N_MAX];

Point Inters(Point A, Point B, int x) {
  double a = A.y - B.y;
  double b = B.x - A.x;
  double c = - a * A.x - b * A.y;
  return Point(x, (-a * x - c) / b);
}

inline bool trigOrder(Point A, Point B, Point C) {
  return 1LL * (B.x - A.x) * (C.y - A.y) > 1LL * (C.x - A.x) * (B.y - A.y);
}

int main() {
  ifstream f("poligon.in");
  ofstream g("poligon.out");
  
  f >> n >> m;
  
  for(int i = 1; i <= n; i++) {
    int x, y;
    f >> x >> y;
    p[i] = Point(x, y);
  }
  p[n + 1] = p[1];
  
  for(int i = 1; i <= n; i++)
    X.push_back(p[i].x);
  
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  
  int nzones = X.size() - 1;
  
  for(int i = 0; i < nzones; i++) {
    for(int j = 1; j <= n; j++) {
      if(p[j].x <= X[i] && X[i + 1] <= p[j + 1].x) {
        Z[i].push_back(Segment(Inters(p[j], p[j + 1], X[i]), Inters(p[j], p[j + 1], X[i + 1])));
      }
    }
  }
  
  for(int i = 0; i < nzones; i++) {
    for(auto &s : Z[i]) {
      if(s.a.x > s.b.x) {
        swap(s.a, s.b);
      }
    }
  }
  
  for(int i = 0; i < nzones; i++) {
    sort(Z[i].begin(), Z[i].end(), [] (Segment s1, Segment s2) {
      return (s1.a.y + s1.b.y) / 2 - (s2.a.y + s2.b.y) / 2 < -1e-6;
    });
  }
  
  int ans = 0;
  while(m--) {
    int x, y;
    Point pt;
    
    f >> x >> y;
    
    pt = Point(x, y);
    
    if(x < X.front() || x > X.back())
      continue;
      
    int px = upper_bound(X.begin(), X.end(), x) - X.begin() - 1;
    int py = Z[px].end() - upper_bound(Z[px].begin(), Z[px].end(), pt, [] (Point pt, Segment s) {
                return 1LL * (s.b.x - s.a.x) * (pt.y - s.a.y) < 1LL * (pt.x - s.a.x) * (s.b.y - s.a.y);
              }) + 1;
                  
    if(py & 1)
      ans++;
  }
  
  g << ans << '\n';
  return 0;
}