Editorial for Bedao Grand Contest 16 - Giấy vụn trên đường


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Với một cặp số cố định ~i~ và ~j~ khác nhau, gọi ~b_i'=-b_i~ giá trị được cực đại hóa của hàm ~f~ có thể biến đổi như sau:

$$\begin{align*}\Delta a \cos x + \Delta b \sin x &= (a_i \cos x - (- b_i) \sin x) - (a_j \cos x - (- b_j) \sin x) \\ &= (a_i \cos x - b_i' \sin x) - (a_j \cos x - b_j' \sin x) \end{align*}$$

Nhắc lại công thức xoay một điểm có tọa độ ~(x, y)~ một góc ~\theta~ trên hệ tọa độ Descartes:

$$\begin{bmatrix} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} x \cos \theta - y \sin \theta \\ x \sin \theta + y \cos \theta \end{bmatrix}$$

Nếu ta xem các cặp giá trị ~P_i := (a_i, b_i')~ là một điểm trên hệ tọa độ, bản chất của giá trị được cực đại hóa của hàm ~f~ là hiệu hoành độ của 2 điểm ~P_i~ và ~P_j~ sau khi xoay một góc ~x~ (rad).

Dễ nhận thấy khi ta chỉ cần quan tâm đến các điểm nằm trên bao lồi.

Dễ nhận thấy sau khi xoay, phải có ít nhất một cạnh của bao lồi vuông góc với ~Ox~.

Lưu ý: Số đỉnh trên bao lồi không quá ~\sqrt[3]{2 \times 10^5}^2~.

Giải thuật đơn giản chỉ cần xét hết các cạnh của bao lồi. Sau đó tìm hệ số góc của cạnh đó để tìm ra giá trị góc cần xoay ~x~, sau đó truyền ~x~ và các đỉnh của bao lồi vào hàm ~f~ và lấy cực tiểu.

Lưu ý: Chi phí mỗi lần tính hàm ~f~: ~O(\text{số đỉnh trên bao lồi})~.

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

typedef complex<double> point;
const double pi = acos(-1.0);

const int N = 1e6 + 5;

int n;
int a[N], b[N];

point rotate(const point &p, double angle) {
    return p * polar(1.0, angle);
}

double find_angle(const point &a, const point &b) {
    // a_x' = a_x * cos(angle) - a_y * sin(angle)
    // b_x' = b_x * cos(angle) - b_y * sin(angle)
    // let d_x = a_x - b_x
    // let d_y = a_y - b_y
    // a_x' = b_x'
    // a_x * cos(angle) - a_y * sin(angle) = b_x * cos(angle) - b_y * sin(angle)
    // cos(angle) * (a_x - b_x) = sin(angle) * (a_y - b_y
    // cos(angle) * d_x = sin(angle) * d_y
    // d_x / d_y = tan(angle)
    // angle = atan(d_x / d_y)
    double dx = a.real() - b.real();
    double dy = a.imag() - b.imag();
    if (dy == 0) {
        return pi / 2;
    }
    return atan(dx / dy);
}

double f(double angle, vector<point> &hull) {
    double min_x = 1e18, max_x = -1e18;
    for (auto p : hull) {
        auto q = rotate(p, angle);
        min_x = min(min_x, q.real());
        max_x = max(max_x, q.real());
    }
    return max_x - min_x;
}

double cross(const point &a, const point &b) {
    return (conj(a) * b).imag();
}

double dot(const point &a, const point &b) {
    return (conj(a) * b).real();
}

vector<point> convexhull(vector<point> &points) {
    vector<point> hull;
    sort(points.begin(), points.end(), [](point a, point b) {
        return a.real() < b.real() || (a.real() == b.real() && a.imag() < b.imag());
    });
    int n = points.size();
    int hsize = 0, hmin = 1;
    for (int i = 0; i < n; ++i) {
        while (hsize > hmin && cross(hull[hsize - 1] - hull[hsize - 2], points[i] - hull[hsize - 2]) <= 0) {
            hull.pop_back();
            hsize--;
        }
        hull.push_back(points[i]);
        hsize++;
    }
    hmin = hsize;
    for (int i = n - 2; i >= 0; --i) {
        while (hsize > hmin && cross(hull[hsize - 1] - hull[hsize - 2], points[i] - hull[hsize - 2]) <= 0) {
            hull.pop_back();
            hsize--;
        }
        hull.push_back(points[i]);
        hsize++;
    }
    return hull;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
    }
    cin >> n;
    vector<point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        points[i] = {a[i], -b[i]};
    }
    auto hull = convexhull(points);
    double result = 1e18;
    for (int i = 0; i + 1 < (int)hull.size(); ++i) {
        double angle = find_angle(hull[i], hull[i + 1]);
        result = min(result, f(angle, hull));
    }
    cout << fixed << setprecision(10) << result << '\n';
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.