Cod sursa(job #1747155)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 24 august 2016 16:16:55
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
 
using namespace std;
 
const int kMaxN = 805;
const double kEps = 1e-6;

int Compare(double a, double b) {
  if(a - b > kEps) return 1;
  if(b - a > kEps) return -1;
  return 0;
}

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

struct Segment {
  Point a;
  Point b;
  Segment() {}
  Segment(Point _a, Point _b) { a = _a; b = _b; }
  Point Middle() const { return Point((a.x + b.x) / 2, (a.y + b.y) / 2); }
  inline bool operator <(Segment const& other) const { return Compare(Middle().y, other.Middle().y) == -1; }
};

int N, Q;
Point P[kMaxN];
vector<int> xCoords;
vector<vector<Segment>> Strips;

int CrossProduct(Point a, Point b, Point c) {
  double termFi = (b.x - a.x) * (c.y - a.y);
  double termSe = (b.y - a.y) * (c.x - a.x);
  return (Compare(termFi, termSe) == -1 ? -1 : Compare(termFi, termSe) == 0 ? 0 : 1);
}

int main() {
  ifstream fin("poligon.in");
  ofstream fout("poligon.out");
  
  fin >> N >> Q;
  for(int i = 1; i <= N; i++) {
    fin >> P[i].x >> P[i].y;
    xCoords.push_back(P[i].x);
  }
  
  sort(xCoords.begin(), xCoords.end());
  xCoords.erase(unique(xCoords.begin(), xCoords.end()), xCoords.end());
  
  for(int i = 0; i < xCoords.size() - 1; i++) {
    Strips.push_back(vector<Segment>());
    for(int j = 1; j <= N; j++) {
      Point pHere = P[j];
      Point pThere = P[(j == N ? 1 : j + 1)];
      if(pHere.x > pThere.x) swap(pHere, pThere);
      if(pHere.x <= xCoords[i] && xCoords[i] < pThere.x) {
        int64_t a = pHere.y - pThere.y;
        int64_t b = pThere.x - pHere.x;
        int64_t c = -(a * pHere.x + b * pHere.y);
        double yHere = -(1.0 * a * xCoords[i] + c) / b;
        double yThere = -(1.0 * a * xCoords[i + 1] + c) / b;
//        cerr << "Adding segment " << j << " " << (j == N ? 1 : j + 1) << '\n';
//        cerr << "The strip is " << xCoords[i] << " " << xCoords[i + 1] << "\n";
//        cerr << "The intersection coordinates are " << yHere << " " << yThere << "\n";
        Strips.back().push_back(Segment(Point(xCoords[i], yHere), Point(xCoords[i + 1], yThere)));
      }
    }
    sort(Strips.back().begin(), Strips.back().end());
  }
  
//  for(int i = 0; i < Strips.size(); i++) {
//    cerr << "Strip #" << i << "\n";
//    for(auto x : Strips[i])
//      cerr << x.a.x << " " << x.a.y << " --> " << x.b.x << " " << x.b.y << "\n";
//  }
  
  int solCnt = 0;
  while(Q--) {
    int x, y;
    fin >> x >> y;
    if(x < xCoords.front() || xCoords.back() < x) continue;
    int sId = lower_bound(xCoords.begin(), xCoords.end(), x) - xCoords.begin() - 1;
    if(sId == -1) sId++;
    
//    cerr << sId << " was " << sId + 1 << "\n";
    
    int lef = 0, rig = Strips[sId].size() - 1;
    bool colinear = 0;
    while(lef <= rig) {
      int med = (lef + rig) >> 1;
      int sgn = CrossProduct(Strips[sId][med].a, Strips[sId][med].b, Point(x, y));
      if(!sgn) colinear = 1, lef = rig + 1;
      else if(sgn < 0) rig = med - 1;
      else if(sgn > 0) lef = med + 1;
    }  
    if((lef & 1) || colinear) solCnt++;
  }
  
  fout << solCnt << "\n";
  return 0;
}