Cod sursa(job #1220352)

Utilizator vlad_DVlad Dumitriu vlad_D Data 17 august 2014 02:50:52
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.89 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
struct segment {
  int x0, y0, x1, y1;
  int A, B, C;
  segment(int x0, int y0, int x1, int y1) : x0(x0), y0(y0), x1(x1), y1(y1) {
    if (x1 < x0) { swap(x0, x1); swap(y0, y1); }
    A = y1 - y0;
    B = x0 - x1;
    C = A * x0 + B * y0;
  }
  segment() {}
  int maxy() { return max(y0, y1); }
};
struct fasie {
  int x0, x1;
  vector<pair<double, segment> > v; 
  fasie(int x0, int x1) : x0(x0), x1(x1) {}
};

inline int intersect(const fasie& f, const segment& s) {
  return min(s.x0, s.x1) <= f.x0 && f.x1 <= max(s.x0, s.x1);
}

bool operator<(const segment& a, const segment& b) {
  return false;
}

vector<pair<int, segment> > vert[60001 * 2];
vector<fasie> f;
vector<segment> s;
int N, M;
int px[801 * 2], py[801 * 2];
set<int> all_x;
vector<int> unic_x;
fasie* whichF[60001 * 2];

int query(int x, int y) {
  return 0;
  // segment vertical?
  int p = upper_bound(vert[x].begin(), vert[x].end(), make_pair(y, segment())) - vert[x].begin() - 1;
  if (p >= 0 && y <= vert[x][p].second.maxy()) return 1;
  // in fasie.
  fasie* fp = whichF[x];
  if (fp == NULL || fp->v.size() == 0) return 0;
  int cnt = 0;
  int a = 0, b = fp->v.size() - 1; 
  while (a <= b) {
    int mid = (a + b) / 2;
    const segment& seg = fp->v[mid].second;
    double ys = double(seg.C - seg.A * x) / seg.B;
    if (double(y) > ys - 1e-09) { cnt = mid + 1; a = mid + 1; }
    else b = mid - 1;
  }
  return cnt % 2;
}
int main() {
 freopen("poligon.in", "r", stdin);
 freopen("poligon.out", "w", stdout);

 scanf("%d %d", &N, &M);
 for (int i = 0; i < N; ++i) {
   scanf("%d %d", &px[i], &py[i]);
   all_x.insert(px[i]);
 }
 unic_x.assign(all_x.begin(), all_x.end());

 // build segmente.
 for (int i = 0; i < N; ++i) {
   int j = (i + 1) % N;
   segment sn(px[i], py[i], px[j], py[j]);
   if (px[i] == px[j]) {
     vert[px[i]].push_back(make_pair(min(py[i], py[j]), sn));
   } else {
     s.push_back(sn);
     segment p1(px[i], py[i], px[i], py[i]);
     vert[px[i]].push_back(make_pair(py[i], p1));
     segment p2(px[j], py[j], px[j], py[j]);
     vert[px[j]].push_back(make_pair(py[j], p2));
   }
 }
 for (int i = 0; i <= 60000; ++i) sort(vert[i].begin(), vert[i].end());

 // build fasii.
 for (int i = 0; i + 1 < unic_x.size(); ++i) {
   f.push_back(fasie(unic_x[i], unic_x[i+1]));
   fasie* fp = &f[f.size() - 1];
   for (int j = 0; j < s.size(); ++j) if (intersect(*fp, s[j])) {
     double ym = double(s[j].C - s[j].A * fp->x0) / s[j].B +
                 double(s[j].C - s[j].A * fp->x1) / s[j].B;
     fp->v.push_back(make_pair(ym, s[j]));
   }
   sort(fp->v.begin(), fp->v.end());
   for (int x = unic_x[i]; x <= unic_x[i+1]; ++x) whichF[x] = fp;
 }

 int total = 0;
 while (M--) {
   int x, y;
   scanf("%d %d", &x, &y);
   //cerr << x << " " << y << " " << query(x, y) << '\n';
   total += query(x, y);
 }
 printf("%d\n", total);
 return 0;
}