Cod sursa(job #1747184)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 24 august 2016 16:35:39
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.2 kb
#include <fstream>
#include <algorithm>
 
using namespace std;
 
const int kMaxN = 805;
const double kEps = 1e-6;

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

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

int N, Q;
Point P[kMaxN];
vector<int> X;
vector<vector<pair<Point, Point>>> S;

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

int main() {
  ifstream fin("poligon.in");
  
  fin >> N >> Q;
  for(int i = 1; i <= N; i++) {
    fin >> P[i].x >> P[i].y;
    X.push_back(P[i].x);
  }
  P[N + 1] = P[1];
  
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  
  for(int i = 0; i < X.size() - 1; i++) {
    S.push_back(vector<pair<Point, Point>>());
    for(int j = 1; j <= N; j++) {
      bool toSwap = 0;
      if(P[j].x > P[j + 1].x) swap(P[j], P[j + 1]), toSwap = 1;
      if(P[j].x <= X[i] && P[j + 1].x > X[i]) {
        int64_t a = P[j].y - P[j + 1].y;
        int64_t b = P[j + 1].x - P[j].x;
        int64_t c = - (a * P[j].x + b * P[j].y);
        S.back().emplace_back(Point(X[i], -(1.0 * a * X[i] + c) / b), 
                                   Point(X[i + 1], -(1.0 * a * X[i + 1] + c) / b));
      }
      if(toSwap) swap(P[j], P[j + 1]);
    }
    sort(S.back().begin(), S.back().end(), [] (pair<Point, Point> const& a, pair<Point, Point> const& b) {
            return Compare(a.first.y + a.second.y, b.first.y + b.second.y) < 0;
         });
  }
  
  int solCnt = 0;
  while(Q--) {
    int x, y;
    fin >> x >> y;
    
    int sId = upper_bound(X.begin(), X.end(), x) - X.begin() - 1;
    if(0 <= sId && sId <= S.size()) {
      int L = 0, R = S[sId].size() - 1;
      while(L <= R) {
        int M = (L + R) >> 1;
        int Sgn = Det(S[sId][M].first, S[sId][M].second, Point(x, y));
        if(!Sgn) { L = 1; break; }
        else if(Sgn < 0) R = M - 1;
        else L = M + 1;
      }
      solCnt += (L & 1);
    }
  }
  
  ofstream("poligon.out") << solCnt << "\n";
  return 0;
}