Cod sursa(job #952695)

Utilizator primulDarie Sergiu primul Data 23 mai 2013 20:14:20
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 8.57 kb
/*
 Catalin-Stefan Tiseanu
  
 Pre-written code is assembled from various sources found online.
 Big thanks to the community for that !
 */
 
// Pre-written code below
 
using namespace std;
 
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
#include <unordered_map>
 
//#define DEBUG
 
#ifdef DEBUG
#define debug(args...)            {dbg,args; cerr<<endl;}
#else
#define debug(args...)              // Just strip off all debug tokens
#endif
 
struct debugger
{
  template<typename T> debugger& operator , (const T& v)
  {
  cerr<<v<<" ";
  return *this;
  }
} dbg;
 
// templates
template<typename T> int size(const T& c) { return int(c.size()); }
template<typename T> T abs(T x) { return x < 0 ? -x : x; }
template<typename T> T sqr(T x) { return x*x; }
template<typename T> bool remin(T& x, T y) { if (x <= y) return false; x = y; return true; }
template<typename T> bool remax(T& x, T y) { if (x >= y) return false; x = y; return true; }
 
// misc
#define EPSILON              1e-7
 
// types
typedef long long            int64;
typedef unsigned long long   uint64;
 
// shortcuts
#define all(_xx)             _xx.begin(), _xx.end()
 
#define pb                   push_back
#define vi                   vector<int>
#define vpii                 vector<pair<int,int> >
#define vpdd                 vector<paid<double,double> >
 
#define pii                  pair<int,int>
#define pdd                  pair<double, double>
#define mp(XX, YY)           make_pair(XX, YY)
#define fi                   first
#define se                   second
 
#define ll                   long long
#define SS                   stringstream
 
// for loops
#define re(II, NN)           for (int II(0), _NN(NN); (II) < (_NN); ++(II))
#define fod(II, XX, YY)      for (int II(XX), _YY(YY); (II) >= (_YY); --(II))
#define fo(II, XX, YY)       for (int II(XX), _YY(YY); (II) <= (_YY); ++(II))
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
 
// Useful hardware instructions
#define bitcount             __builtin_popcount
#define gcd                  __gcd
 
// Useful all around
#define checkbit(n,b)        ( (n >> b) & 1)
#define DREP(a)              sort(all(a));a.erase(unique(all(a)),a.end())
#define INDEX(arr,ind)       (lower_bound(all(arr),ind)-arr.begin())
 
// Code written during the competition below
 
#define MAX_N 812
#define ADD_VAL 0
 
#include <unordered_map>
 
int N, M, res;
vpii vertex;
pii edge_left[MAX_N], edge_right[MAX_N];
vi line[MAX_N], unique_x, on_line[MAX_N];
map<pii, char> vertex_map;
pdd edge_intersect_left[MAX_N], edge_intersect_right[MAX_N];
 
int64 cross(const pii& a, const pii& b) {return (int64)a.fi * b.se - a.se * b.fi;}
double cross(pdd a, pdd b) {return a.fi * b.se - a.se * b.fi;}
int64 area(const pii& a, const pii& b, const pii& c) {
  return (int64)cross(a, b) + cross(b, c) + cross(c, a);
}
double area(pdd a, pdd b, pdd c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}
bool isLeft(const pii& a, const pii& b, const pii& c){return area(a, b, c) > 0;}
bool isLeft(const pdd& a, const pdd& b, const pdd& c){return area(a, b, c) > 0;}
 
pdd clip_edge_on_vertical(pii p1, pii p2, double alpha) {
  return mp(alpha, 1.0 * p1.se +
  1.0 * (p2.se - p1.se) *
  (alpha - p1.fi) /
  (p2.fi - p1.fi));
}
 
inline int wn_Point(pii P, vpii Poligon){
  int wn = 0;
  re(i, size(Poligon) - 1) {
    if (Poligon[i].se <= P.se){ // upward
      if (Poligon[i + 1].se > P.se)
        if (area(Poligon[i], Poligon[i + 1], P) > 0)
          ++wn;
    } else if (Poligon[i].se > P.se){ //downward
      if (Poligon[i + 1].se <= P.se)
        if (area(Poligon[i], Poligon[i + 1], P) < 0)
          --wn;
    }
    if (min(Poligon[i].fi, Poligon[i+1].fi) <= P.fi &&
        max(Poligon[i].fi, Poligon[i+1].fi) >= P.fi &&
        area(Poligon[i], Poligon[i + 1], P) == 0)
        return 1;
  }
  return wn;
}
 
 
inline int check_line(pii p, int pos) {
  debug("* is on <line>", unique_x[pos]);
  if (pos == 0 || !size(line[pos]))
    return 0;
  int line_nr = lower_bound(all(line[pos]), p,
                            [](int el, pii p){return area(edge_left[el],
                                                          edge_right[el],
                                                          p) > 0;})
  - line[pos].begin();
  debug("* is on line number", line_nr);
  if (line_nr >= size(line[pos]))
    return 0;
  if (area(edge_left[line[pos][line_nr]],
           edge_right[line[pos][line_nr]],
           p) == 0)
    return 1;
  return line_nr % 2 == 1;
}
 
inline int check_on_line(pii p, int pos) {
  debug("* is on <on_line>", unique_x[pos]);
  if (!size(on_line[pos]))
    return 0;
  int line_nr = lower_bound(all(on_line[pos]), p.se,
                            [](int el, int my_se){return edge_left[el].se < my_se;})
  - on_line[pos].begin();
  debug("* is on line number", line_nr);
  if (line_nr >= size(on_line[pos]))
      return 0;
  return p.se <= edge_left[on_line[pos][line_nr]].se &&
  p.se >= edge_right[on_line[pos][line_nr]].se;
}
 
inline int query(pii p) {
  debug("querying", p.fi, p.se);
  if (vertex_map.count(p)) {
    debug("-> it's a vertex");
    return 1;
  }
  int pos = lower_bound(all(unique_x), p.fi) - unique_x.begin();
  if (unique_x[pos] > p.fi)
    return check_line(p, pos - 1);
  else
    return check_line(p, pos) || check_on_line(p, pos);
}
 
void preprocess() {
  set<int> s = {-60001, 60001};
  re (i, N)
    s.insert(vertex[i].fi);
  unique_x = vi(all(s));
   
  re (i, N) {
    vertex_map[vertex[i]] = 1;
    if (vertex[i].fi < vertex[i+1].fi ||
        (vertex[i].fi == vertex[i+1].fi && vertex[i].se > vertex[i+1].se))
      edge_left[i] = vertex[i], edge_right[i] = vertex[i + 1];
    else
      edge_left[i] = vertex[i + 1], edge_right[i] = vertex[i];
  }
   
  fo (j, 1, size(unique_x) - 2) {
    re (i, N) {
      if (edge_left[i].fi <= unique_x[j] &&
          edge_right[i].fi >= unique_x[j+1]) {
        line[j].pb(i);
 
        edge_intersect_left[i] =
          clip_edge_on_vertical(edge_left[i], edge_right[i], unique_x[j]);
        edge_intersect_right[i] =
          clip_edge_on_vertical(edge_left[i], edge_right[i], unique_x[j+1]);
 
        debug(unique_x[j], i, edge_intersect_left[i].se, edge_intersect_right[i].se);
      } else if (edge_left[i].fi == unique_x[j] &&
          edge_right[i].fi == unique_x[j]) {
        on_line[j].pb(i);
      }
    }
     
    if (size(line[j])) {
      sort(all(line[j]), [](int x, int y){
        return (edge_intersect_left[x].se + EPSILON <
                edge_intersect_left[y].se) ||
               (edge_intersect_right[x].se <
                edge_intersect_right[y].se);});
  }
 
  fo (l, 1, size(unique_x) - 2)
    if (size(on_line[l]))
    sort(all(on_line[l]), [](int x, int y){return edge_left[x].se <
                                                  edge_left[y].se;});
  }
#ifdef DEBUG
  fo (l, 1, size(unique_x) - 2) {
    debug("line = ", unique_x[l]);
    re (j, size(line[l]))
      debug(line[l][j]);
  }
   
  fo (l, 1, size(unique_x) - 2) {
    debug("on_line = ", unique_x[l]);
    re (j, size(on_line[l]))
    debug(on_line[l][j]);
  }
#endif
}
 
int main() {
  freopen("poligon.in", "r", stdin);
  freopen("poligon.out", "w", stdout);
   
  scanf("%d %d", &N, &M);
  vertex.resize(N);
   
  re(i, N) {
    scanf("%d %d", &vertex[i].fi, &vertex[i].se);
    vertex[i].fi += ADD_VAL, vertex[i].se += ADD_VAL;
  }
  vertex.pb(vertex[0]);
 
#ifdef DEBUG
  re (i, N) debug("segment", i, vertex[i].fi, vertex[i].se);
#endif
 
  preprocess();
 
  re (i, M) {
    int a, b;
    scanf("%d %d", &a, &b);
    a += ADD_VAL, b += ADD_VAL;
    res += query(mp(a,b));
  }
 
  // stress test
/*
  fo (a, -20,20) fo (b, -20, 20)
  if (!vertex_map.count(mp(a,b))) {
    pii p(a, b);
    int brute_res = wn_Point(p, vertex);
    int fast_res = query(p);
    if (brute_res != fast_res) {
      debug(">>ERROR for:", p.fi, p.se, "fast", fast_res, " brute", brute_res);
      assert(brute_res == fast_res);
    }
  }
*/
  printf("%d\n", res);
   
  return 0;
}