AOJ 1629 正三角形の柵 (Equilateral Triangular Fence)

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1629&lang=ja

解法

底辺の y 座標を決めうったとする．これを \(y_l\) とおく．
\(y \geq y_l\) をみたすある点 \((x, y)\) が正三角形の内部にあるための条件は，底辺の左端と右端の x 座標（それぞれ \(l_x, r_x\) とおく）が
\[
x - y/\sqrt{3} + y_l/\sqrt{3} \leq lx \land rx \leq x + y/\sqrt{3} - y_l/\sqrt{3}
\]
を満たすときである．これは1次元上の条件である．

したがって，前処理として \(x - y/\sqrt{3}, x + y/\sqrt{3}\) のそれぞれで点をソートした列をもっておき，左端を決めて右端を伸ばしていくしゃくとりを行えば解くことができる．
\(y_l/\sqrt{3}\) の分は全体に同じだけかかるオフセットなので，前処理のソートによる順番に影響しない．区間さえ求めたら，オフセット分を長さから引いてやれば良い．

特に何も考えず実装すると，計算量は \(O(nk + n\log n)\) となる．

ソースコード

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

constexpr double eps = 1e-9;
constexpr double inf = 1e9;
const double sq3 = sqrt(3);

int main() {
    cout << fixed << setprecision(10);

    int n;
    while(cin >> n, n) {
        int k; cin >> k;

        vector<int> x(n), y(n);
        vector<pair<double, int>> lx(n), rx(n);
        for(int i = 0; i < n; ++i) {
            cin >> x[i] >> y[i];
            lx[i] = make_pair(x[i] - y[i] / sq3, i);
            rx[i] = make_pair(x[i] + y[i] / sq3, i);
        }
        sort(lx.begin(), lx.end());
        sort(rx.begin(), rx.end());

        double res = inf;
        vector<int> used(n);
        for(int ly = 1; ly <= 10000; ++ly) {
            if((int)lx.size() < n - k) break;
            fill(used.begin(), used.begin() + lx.size(), 0);
            int l = 0, r = 0, cnt = 0;
            while(l < (int)lx.size()) {
                while(cnt < n - k && r < (int)rx.size()) {
                    cnt += ++used[rx[r++].second] == 1;
                }
                if(cnt == n - k) {
                    res = min(res, rx[r - 1].first - lx[l].first - 2 * ly / sq3);
                }
                const double cur_x = lx[l].first;
                while(l < (int)lx.size() && abs(cur_x - lx[l].first) < eps) {
                    cnt -= --used[lx[l++].second] == 0;
                }
            }

            auto rm_pred = [&] (auto const& p) { return y[p.second] == ly; };
            lx.erase(remove_if(lx.begin(), lx.end(), rm_pred), lx.end());
            rx.erase(remove_if(rx.begin(), rx.end(), rm_pred), rx.end());
        }

        cout << 3 * res << endl;
    }
}