### Mở bài
Do dạo này Hà Nội mùa nồm nên tính mình hơi mát mát, xong viết cái blog này :sob:

### Phương pháp nhân tử Lagrange
Trong kì học đầu tiên ở HUST, mình được thầy Nguyễn Xuân Thảo chỉ cho cái này ở bài cuối cùng trong môn GT1. Cụ thể là để tìm một cực trị của hàm nhiều biến $f(x_1, x_2, ..., x_n)$ dưới điều kiện $g(x_1, x_2, ..., x_n) = C$.

Ta thêm một biến Lagrange $\lambda$ vào và tìm các điểm tới hạn của hàm $L(x_1, x_2, ..., x_n, \lambda) = f(x_1, x_2, ..., x_n) + \lambda \times (g(x_1, x_2, ..., x_n) - C)$.

### Vậy nó có ứng dụng gì trong Lập trình
- Mình chịu, chỉ là giải được một bài hay hay bằng phương pháp này nên xin lỗi thầy Thảo vì em lười học T_T

#### Problem
**[UVA-12407](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3838)**: Speed Zones

- Tóm tắt: Chia mặt phẳng toạ độ Oxy thành $N$ phần $N \le 100$, mỗi phần có chiều rộng $100$ đơn vị, nếu bạn đứng ở điểm có tung độ trong $[100 \times (i - 1), 100 \times i)$ $(1 \le i < N)$ bạn có thể di chuyển với vận tốc $S_i$ $(1 \le S_i \le 10000)$. Tìm thời gian ngắn nhất để di chuyển từ $(0, 0)$ đến $(D, 100 \times N)$.

Ta có thể thấy rằng:
- Thời gian đi ngắn nhất là thời gian mình đi thẳng từ $1$ điểm $(x_1, y_1)$ đến điểm $(x_2, y_2)$.
- Cơ mà đi thẳng từ $(0, 0)$ đến $(D, 100 \times N)$ thì sẽ sai. Nếu ta coi đường đi của vật là $1$ tia sáng thì theo Snell thời gian ngắn nhất luôn bằng với thời gian $1$ tia sáng đi từ $A$ đến $B$, góc khúc xạ của tia sáng giữa $2$ môi trường khác nhau tính bằng Định Luật Snell $(\frac{\sin{\theta_1}}{\sin{\theta_2}} = \frac{v_1}{v_2})$, và khả năng là $\theta_1 \ne \theta_2$ rồi nên có thể tia sẽ không thẳng ([bài này cũng có thể giải bằng Snell đó](https://oj.vnoi.info/problem/bedao_g13_e)).
- Cơ mà mình không bàn đến Snell ở đây vì thế nên mình sẽ dùng phương pháp nhân tử Lagrange. Ta cần chia đoạn $[0, D]$ thành $N$ phần $x_1, x_2, ..., x_N$ thoả mãn $0 \le x_1, x_2, ..., x_N$ và $x_1 + x_2 + ... + x_N = D$. Khi đó, bài toán trở thành tìm cực trị của hàm $f_(x_1, x_2, ..., x_N) = \Sigma^{N}_{i = 1} \frac{\sqrt{10000 + x_i^2}}{s_i}$ dưới điều kiện $g_(x_1, x_2, ..., x_N) = \Sigma^{N}_{i = 1} x_i - D$.
- Tính các đạo hàm riêng của $L(x_1, x_2, ..., x_n, \lambda) = f(x_1, x_2, ..., x_n) - \lambda \times g(x_1, x_2, ..., x_n)$:
- $\frac{\partial L}{\partial x_i} = \frac{x_i}{s_i\sqrt{10000 + x_i^2}} - \lambda$.
- $\frac{\partial L}{\partial \lambda} = \Sigma^{N}_{i = 1} x_i - D$.

- Điểm tới hạn thoả mãn:

\begin{cases}
& \frac{x_i}{s_i\sqrt{10000 + x_i^2}} - \lambda = 0 \\
& \Sigma^{N}_{i = 1} x_i = D
\end{cases}

- Tính được: $x_i = \frac{|100\lambda s_i|}{\sqrt{1 - (\lambda s_i)^2}} = \frac{100s_i}{\sqrt{\frac{1}{\lambda^2} - s_i^2}}$.

- Đến đây, mình thấy được với $\lambda$ càng tăng thì $x_i$ cũng tăng theo, do đó $\Sigma^{N}_{i = 1} x_i$ cũng sẽ tăng cùng. Do đó, ta có thể sử dụng chặt nhị phân để tìm $\lambda$ thoả mãn điều kiện $\Sigma^{N}_{i = 1} x_i = D$.

### Code

#include<bits/stdc++.h>
#define fi first
#define sc second
#define task ""
using namespace std;
int t, n, d, s[102];

long double sum(long double T) {
    long double res = 0;
    for (int i = 1; i <= n; ++i)
        res += 100 * T * s[i]/sqrt(1 - T * T * s[i] * s[i]);

    return res;
}

int main() {
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);


    cin >> t;

    for (int i = 1; i <= t; ++i) {
        cin >> n >> d;

        long double lo = 0, hi = 1e9;
        for (int i = 1; i <= n; ++i) {
            cin >> s[i];
            hi = min(hi, sqrt((long double) 1.0/(s[i] * s[i])));
        }

        for (int i = 1; i <= 100; ++i) {
            long double mid = (lo + hi)/2;

            if (sum(mid) <= d)
                lo = mid;
            else
                hi = mid;
        }

        long double L = (lo + hi)/2, ans = 0;


        for (int i = 1; i <= n; ++i)
            ans += sqrt(10000 + (10000 * L * L * s[i] * s[i])/(1 - L *L * s[i] * s[i]))/s[i];

        cout << fixed << setprecision(6) << "Case " << i << ": " << ans << '\n';
    }
}

### Kết bài
Chúc mọi người có người yêu :sunglasses: