Cod sursa(job #2310391)

Utilizator NeredesinI am not real Neredesin Data 31 decembrie 2018 14:21:41
Problema Poligon Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in("poligon.in");
ofstream out("poligon.out");

const int NMAX = 8 * 1e2 + 10;

int n, m;
int res;
int indx;
int i, j;

int a[1 + NMAX];
int b[1 + NMAX];
int c[1 + NMAX];

int x[1 + NMAX];

int aux[1 + NMAX];

double slope[1 + NMAX];

bool found;

vector < int > strip[1 + NMAX];

pair < int, int > v[1 + NMAX];
pair < int, int > q;

inline bool cmp(int a, int b) {
  return (slope[a] * (x[i] + x[i + 1]) + 2 * aux[a] < slope[b] * (x[i] + x[i + 1]) + 2 * aux[b]);
}

inline bool check_data(int pos, pair < int, int > query) {
  if(a[pos] * query.first + b[pos] * query.second + c[pos] == 0)
    found = true;

  return (query.second >= slope[pos] * query.first + aux[pos]);
}

int main()
{
  in >> n >> m;
  for(i = 1; i <= n; i++) {
    in >> v[i].first >> v[i].second;
    x[i] = v[i].first;
  }
  v[n + 1] = v[1];

  indx = 1;
  sort(x + 1, x + n + 1);

  for(i = 1; i <= n; i++) {
    if(x[i] != x[i - 1]) {
      x[++indx] = x[i];
    }
  }
  x[indx + 1] = 0;

  for(i = 1; i <= n; i++) {
    a[i] = v[i + 1].second - v[i].second;
    b[i] = v[i].first - v[i + 1].first;

    c[i] = -(a[i] * v[i].first + b[i] * v[i].second);
    slope[i] = -1.0 * a[i] / b[i];
    aux[i] = -1.0 * c[i] / b[i];
  }

  for(i = 1; i <= indx; i++) {
    for(j = 1; j <= n; j++)
      if(x[i] >= min(v[j].first, v[j + 1].first) && x[i] < max(v[j].first, v[j + 1].first))
        strip[i].push_back(j);

    sort(strip[i].begin(), strip[i].end(), cmp);
  }

  for(int qu = 1; qu <= m; qu++) {
    in >> q.first >> q.second;

    if(q.first < x[1] || q.first > x[indx])
        continue;

    found = false;

    int step;
    for(step = 1024, i = 0; step > 0; step >>= 1)
      if(i + step <= indx && x[i + step] < q.first)
        i += step;

    for(step = 1024, j = 0; step > 0; step >>= 1)
      if(j + step <= strip[i].size() && check_data(strip[i][j + step - 1], q))
        j += step;

    if(j % 2 == 1 || found == true)
      res++;
  }

  out << res << '\n';

  in.close();
  out.close();

  return 0;
}