Cod sursa(job #945223)

Utilizator ZeusCatalin Tiseanu Zeus Data 30 aprilie 2013 22:31:07
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.78 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

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;

int64 cross(pii a, pii b) {return (int64)(a.fi * b.se) - a.se * b.fi;}
int64 area(pii a, pii b, pii c) {
  return cross(a, b) + cross(b, c) + cross(c, a);
}

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) {
    --pos;
    debug("* is on <line>", pos);
    if (pos == 0)
      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 (area(edge_left[line[pos][line_nr]],
                edge_right[line[pos][line_nr]],
                p) == 0)
      return 1;
    return line_nr % 2 == 1;
  } else {
    debug("* is on <on_line>", pos);
    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);
    return p.se <= edge_left[on_line[pos][line_nr]].se &&
           p.se >= edge_right[on_line[pos][line_nr]].se;
  }
}

void preprocess() {
  set<int> s = {-1, 60001};
  re (i, N)
    s.insert(vertex[i].fi);
  unique_x = vi(all(s));
  re (i, N) {
    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];
  }
  re (i, N) {
    vertex_map[vertex[i]] = 1;
    fo (j, 1, size(unique_x) - 2) {
      if (edge_left[i].fi <= unique_x[j] &&
          edge_right[i].fi >= unique_x[j+1]) {
        line[j].pb(i);
      } else if (edge_left[i].fi == unique_x[j] &&
                 edge_right[i].fi == unique_x[j]) {
        on_line[j].pb(i);
      }
    }
  }
  fo (l, 1, size(unique_x) - 2)
    sort(all(line[l]), [](int x, int y){return area(edge_left[x],
                                               edge_right[x],
                                               edge_left[y]) > 0;});
  
  fo (l, 1, size(unique_x) - 2)
  sort(all(on_line[l]), [](int x, int y){return edge_left[x].se <
                                                edge_left[y].se;});
  
  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]);
  }
}

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.pb(vertex[0]);

  re (i, N) debug(vertex[i].fi, vertex[i].se);

  preprocess();
  
  re (i, M) {
    int a, b, cur;
    scanf("%d %d", &a, &b);
    res += query(mp(a,b));
  }
  
  printf("%d\n", res);
  
  return 0;
}