CodeForces 406D

cf_406d.cpp

#include <cstdio>
#include <cstdlib>
#include <vector>

const int N = 100000, TREE_HEIGHT = 17;

struct point {
  long long x, y;
  int multi(const point &a, const point &b) {
    // printf("Multiply a(%d, %d) with b(%d, %d)",
    //     a.x - x, a.y - y, b.x - x, b.y - y);
    long long x1 = a.x - x, x2 = b.x - x, y1 = a.y - y, y2 = b.y - y;
    long long result = x1 * y2 - x2 * y1;
    // printf(", result: %d.\n", result);
    if (result > 0)
      return 1;
    else if (result < 0)
      return -1;
    return 0;
  }
};

struct node {
  int child;
  node *next;
  node(int _child, node *_next) : child(_child), next(_next) { }
};

int deep_data[N + 1] = { 0 };

int n, *deep = deep_data + 1, ancestor[N][TREE_HEIGHT + 1] = { 0 };
point pt[N];
node *children[N] = { 0 };

void add_child(int parent, int child) {
  children[parent] = new node(child, children[parent]);
}

int lca(int u, int v) {
  if (deep[u] < deep[v]) {
    int t = u;
    u = v;
    v = t;
  }

  // printf("---\nComputing LCA of u=%d and v=%d\n", u, v);

  for (int i = TREE_HEIGHT; i >= 0; i--) {
    if (deep[ancestor[u][i]] >= deep[v]) {
      u = ancestor[u][i];
      // printf("Trace u to %d\n", u);
      if (deep[u] == deep[v])
        break;
    }
  }

  // printf("Tracing complete, now u=%d and v=%d\n", u, v);

  if (u == v)
    return u;

  for (int i = TREE_HEIGHT; i >= 0; i--) {
    if (ancestor[u][i] != ancestor[v][i]) {
      u = ancestor[u][i];
      v = ancestor[v][i];
      // printf("Iterating, u=%d and v=%d\n", u, v);
    }
  }

  // printf("Computing complete, result: %d\n", ancestor[u][0]);
  return ancestor[u][0];
}

void init_ancestors() {
  // compute ancestor infos
  for (int i = 1; i <= TREE_HEIGHT; i++) {
    for (int j = 0; j < n; j++) {
      if (ancestor[j][i - 1] != -1)
        ancestor[j][i] = ancestor[ancestor[j][i - 1]][i - 1];
      else
        ancestor[j][i] = -1;
    }
  }

  // printf("     ");
  // for (int i = 1; i <= n; i++)
  //   printf("%d ", i);
  // putchar('\n');
  // for (int i = 0; i <= TREE_HEIGHT; i++) {
  //   printf(i > 9 ? "2^%d " : "2^%d  ", i);
  //   for (int j = 0; j < n; j++)
  //     printf("%d ", ancestor[j][i] + 1);
  //   putchar('\n');
  // }
}

void dfs(int t = n - 1, int layer = 0) {
  deep[t] = layer;
  for (node *p = children[t]; p; p = p->next)
    dfs(p->child, layer + 1);
}

void read_data() {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%I64d%I64d", &pt[i].x, &pt[i].y);
    ancestor[i][0] = -1;
  }
}

void build_tree() {
  std::vector<int> q;
  q.push_back(n - 1);
  for (int i = n - 2; i >= 0; i--) {
#define prev q.back()
#define pprev q[q.size() - 2]
    // printf("---\nCalcualting #%d\n", i);
    while (q.size() > 1 && pt[i].multi(pt[prev], pt[pprev]) > 0)
      q.pop_back();
    ancestor[i][0] = q.back();
    add_child(q.back(), i);
    q.push_back(i);
    // printf("Set parent of %d to %d\n", q.back() + 1, ancestor[i][0] + 1);
#undef prev
#undef pprev
  }
  // for (int i = 0; i < n; i++)
  //   printf("%d ", ancestor[i][0] + 1);
  // putchar('\n');
}

void answer() {
  int q, u, v;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    scanf("%d%d", &u, &v);
    int ans = lca(u - 1, v - 1) + 1;
    printf("%d ", ans == 0 ? n : ans);
  }
}

int main() {
  read_data();
  build_tree();
  init_ancestors();
  deep[-1] = -1;
  dfs();

  // puts("---\nDeep:");
  // for (int i = 0; i < n; i++)
  //   printf("%d ", i + 1);
  // putchar('\n');
  // for (int i = 0; i < n; i++)
  //   printf("%d ", deep[i] + 1);
  // putchar('\n');

  answer();
  return 0;
}

/*
6
1 4
2 1
3 2
4 3
6 4
7 4
3
3 1
5 6
2 3
*/