Codeforces Round #238 (Div. 1) D. Hill Climbing

問題文

http://codeforces.com/problemset/problem/406/D

問題概要

山が一直線上に n 山ならんでいる．それぞれの山の座標は x[i]，高さは y[i] である．
山と山にはスロープがかかっている．スロープは以下のようにかかっている．
各山 a は，a の頂上から右（x の正方向）を見たときに見える山で一番右にある山 b とスロープでつながっている．

この山々に対してクエリが m 個投げられる．各クエリは山 a と b を指定してくるので，a と b から右の山にスロープで移動していって，合流する山を答えよ．

・制約
1 <= n <= 10^5
1 <= m <= 10^5
1 <= x[i] <= 10^7
1 <= y[i] <= 10^11
x[i] は相異なる．

解法

スロープを辺と見ると，これは山 n を根とした木になっていることがわかる．
合流する山とは，この根付き木での LCA を求めるということである．

あとはスロープをつなげるだけだが，これは山 n から見ていって，凸包を作るような感じで結んでいけば良い．
候補の山を vector で持っておき，今見ている山の頂上と候補の中で直近の山の頂上を結んだときの傾きで判定すれば良い．
この傾きが増加し続ける限り，その要素を pop_back しながら右の山を見ていく．
増加しなくなったタイミングで打ち切り，その山とスロープをつなげる．
pop_backした山は，後にスロープがかかることは無いのでそれっきりでOK．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

constexpr int INF = 1e9 + 1;

struct edge {
    int from, to;
};

using edges = std::vector<edge>;
using graph = std::vector<edges>;

int main() {
    int n;
    scanf("%d", &n);
    vector<double> x(n), y(n);
    for(int i = 0; i < n; ++i) {
        scanf("%lf %lf", &x[i], &y[i]);
    }

    vector<int> v = {n - 1};
    graph g(n);
    for(int i = n - 2; i >= 0; --i) {
        int j = v.size() - 1;
        double a = (y[v[j]] - y[i]) / (x[v[j]] - x[i]);
        for(int k = j - 1; k >= 0; --k) {
            if(a < (y[v[k]] - y[i]) / (x[v[k]] - x[i])) {
                j = k;
                a = (y[v[k]] - y[i]) / (x[v[k]] - x[i]);
                v.pop_back();
            } else {
                break;
            }
        }
        add_edge(g, i, v[j]);
        v.push_back(i);
    }

    // n - 1 を根にする
    lca L(g, n - 1);
    int m;
    scanf("%d", &m);
    for(int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--; b--;
        if(i != 0) {
            printf(" ");
        }
        printf("%d", L.query(a, b) + 1);
    }
    printf("\n");
}

感想

英文読解に失敗して LCA だと思ってなかった．
辺をはるところが難しい．なんとかバグらせずに通せた．