題解 [ABC130F] Minimum Bounding Box

這題分讨略有點惡心啊。

題面給了一堆運動的點，要求一個時刻時正着覆寫所有點的最小矩形最小。

腦補了一下覺得這是一個單峰函數，于是想着三分，但是又不太确定，是以寫。

模拟一下可以發現，很多點其實是對答案沒有影響的，因為它們的運作速度都一樣，是以在同一個方向上運作的點隻有最左邊和最右邊（最上最下）的是有用的。

那麼就把四個方向上的點都單獨拿出來，然後找出最兩邊的來考慮就行了。

資料範圍已經縮小到了 \(n=4 \times 2 = 8\) 了，怎麼實作呢？

再次觀察運動過程，其實答案在最小的時候肯定是兩個點并到一塊兒了。考慮兩個的相對運動，互相遠離的一定不可能讓答案變小，而一個變大一個變小的要麼最後一個次元減到 \(0\)，要麼一個次元被其它的給約數住，隻剩下一個次元的變化，是以肯定是兩個點撞在同一水準或豎直線線的時候。

1. 兩點在水準方向上相向運動。
2. 兩點在豎直方向上相向運動。
3. 一個往上，一個往左。
4. 一個往上，一個往右。
5. 一個往下，一個往左。
6. 一個往下，一個往右。

混亂的代碼

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#define fi first
#define se second
#define mapa std::make_pair
const int N = 100005;
std::vector<std::pair<int, int> > p[5];
std::vector<std::pair<std::pair<int, int>, int> > vi;
double ans = 1e18;
char st[N][5];
int x[N], y[N], tr[256], n;
double get(double t) {
    if (t < 0) return 1e18;
    double xmax = -1e18, xmin = 1e18, ymax = -1e18, ymin = 1e18;
    for (int i = 1; i <= n; i++) {
        double nx = x[i], ny = y[i];
        if (st[i][0] == 'R') nx += t;
        else if (st[i][0] == 'L') nx -= t;
        else if (st[i][0] == 'U') ny += t;
        else ny -= t;
        xmax = std::max(nx, xmax), xmin = std::min(xmin, nx);
        ymax = std::max(ny, ymax), ymin = std::min(ny, ymin);
    }
    return (xmax - xmin) * (ymax - ymin);
}
int main(){ 
    tr['R'] = 1, tr['L'] = 2, tr['U'] = 3, tr['D'] = 4;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        std::cin >> x[i] >> y[i] >> st[i];
        p[tr[st[i][0]]].push_back(mapa(x[i], y[i]));
    }
    for (int i = 1; i <= 4; i++) {
        int xmax = 0, xmin = 0, ymax = 0, ymin = 0;
        for (int j = 1; j < (int)p[i].size(); j++) {
            if (p[i][j].fi > p[i][xmax].fi) xmax = j;
            if (p[i][j].fi < p[i][xmin].fi) xmin = j;
            if (p[i][j].se > p[i][ymax].se) ymax = j;
            if (p[i][j].se < p[i][ymin].se) ymin = j;
        }
        if (p[i].size()) {
            vi.push_back(mapa(p[i][xmax], i)), vi.push_back(mapa(p[i][xmin], i)), 
            vi.push_back(mapa(p[i][ymax], i)), vi.push_back(mapa(p[i][ymin], i));
        }
    }
    std::cout << std::fixed << std::setprecision(10);
    ans = get(0);
    for (int i_ = 0; i_ < (int)vi.size(); i_++)
        for (int j_ = 0; j_ < (int)vi.size(); j_++) {
            int i = i_, j = j_;
            int op1 = vi[i].se, op2 = vi[j].se;
            if (op1 > op2) std::swap(i, j), std::swap(op1, op2);
            if (op1 * op2 == 2) {
                double t = -1.0 * (1.0 * vi[i].fi.fi - vi[j].fi.fi) / 2;
                ans = std::min(ans, get(t));
            }
            else if (op1 * op2 == 12) {
                double t = -1.0 * (1.0 * vi[i].fi.se - vi[j].fi.se) / 2;
                ans = std::min(ans, get(t));
            }
            if (op1 <= 2) {
                if (op2 == 3) {
                    double t = (vi[i].fi.se - vi[j].fi.se);
                    ans = std::min(ans, get(t));
                }
                else if (op2 == 4) {
                    double t = -(vi[i].fi.se - vi[j].fi.se);
                    ans = std::min(ans, get(t));  
                }
            }
            if (op2 > 2) {
                if (op1 == 1) {
                    double t = -(vi[i].fi.fi - vi[j].fi.fi);
                    ans = std::min(ans, get(t));
                }
                else if (op1 == 2) {
                    double t = (vi[i].fi.fi - vi[j].fi.fi);
                    ans = std::min(ans, get(t));  
                }
            }
        }
    std::cout << ans;
}