Cod sursa(job #1746504)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 23 august 2016 14:23:06
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define fi first
#define se second
#define mp make_pair
#define pi pair<int, int>

using namespace std;

const int kMaxN = 805;

struct Point {
  double x, y;
  Point() {}
  Point(int _x, int _y) : x(_x), y(_y) {}
};

struct Segment {
  Point a, b;
  Segment() {}
  Segment(Point _a, Point _b) : a(_a), b(_b) {}
  Point Middle() { return Point((a.x + b.x) / 2, (a.y + b.y) / 2); }
};

struct Line {
  double a, b, c;
  Line() {}
  Line(double _a, double _b, double _c) : a(_a), b(_b), c(_c) {}
  Line(Point p1, Point p2) {
    a = p1.y - p2.y;
    b = p2.x - p1.x;
    c = (-1) * a * p1.x + (-1) * b * p1.y;
  }
};

double CrossProduct(Point p1, Point p2, Point p3) {
  return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

bool AboveSegment(Point p, Segment s) {
  return CrossProduct(s.a, s.b, p) > 0;
}

int n, q;
Point p[kMaxN];
vector<int> x_coords;
vector<vector<Segment>> strips;

int main() {
  ifstream f("poligon.in");
  ofstream g("poligon.out");
  
  f >> n >> q;
  for(int i = 1; i <= n; i++) {
    f >> p[i].x >> p[i].y;
    x_coords.push_back(p[i].x);
  }
  
  sort(x_coords.begin(), x_coords.end());
  x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
  
  strips.resize(x_coords.size() - 1);
  for(int i = 0; i < x_coords.size() - 1; i++) {
    for(int j = 1; j <= n; j++) {
      Point p_here = p[j];
      Point p_there = (j == n ? p[1] : p[j + 1]);
      
      if(p_here.x > p_there.x)
        swap(p_here, p_there);
      
      if(p_here.x == p_there.x)
        continue;
      
      if(p_here.x <= x_coords[i] && x_coords[i + 1] <= p_there.x) {
        Line seg_line(p_here, p_there);
        double y_here = (-1) * (seg_line.a * p_here.x + seg_line.c) / seg_line.b;
        double y_there = (-1) * (seg_line.a * p_there.x + seg_line.c) / seg_line.b;
        strips[i].push_back(Segment(Point(x_coords[i], y_here), Point(x_coords[i + 1], y_there)));
      }
    }
  }
  
  for(int i = 0; i < strips.size(); i++)
    sort(strips[i].begin(), strips[i].end(), [] (Segment s1, Segment s2) { return s1.Middle().y < s2.Middle().y; });
    
  int good_cnt = 0;
  while(q--) {
    int x, y;
    f >> x >> y;
    
    if(x < x_coords.front() || x > x_coords.back())
      continue;
    
    int id = lower_bound(x_coords.begin(), x_coords.end(), x) - x_coords.begin() - 1;

    int lo = 0, hi = strips[id].size() - 1, mid;
    while(lo <= hi) {
      mid = (lo + hi) / 2;
      if(AboveSegment(Point(x, y), strips[id][mid])) { lo = mid + 1; }
      else hi = mid - 1;
    }
    //t pos = upper_bound(strips[id].begin(), strips[id].end(), Point(x, y), AboveSegment) - strips[id].begin();
    int pos = lo;
    
    //g << pos << " pos\n";
    
    good_cnt += (pos & 1);
  }
  
  g << good_cnt << '\n';
  return 0;
}