Điều kiện

~\sum_{i=1}^{n} (x_iy_i)^2=0~

tương đương với ~x_i~ và ~y_i~ có tích đúng bằng ~0~.

Như vậy ta xem như mình có thể chia mảng ~a~ ra thành ~2~ phần riêng biệt (tương tự với mảng ~b~), giải bài toán tìm max cho mỗi phần rồi cộng lại ta sẽ có được ~V~.

Bài toán cần giải là:

~\left(\sum_{i=1}^{n}a_ix_i\right)\left(\sum_{i=1}^{n}b_ix_i\right)~

sao cho biểu thức đạt max.

Ta gọi ~x_i'~, ~a_i'~, ~b_i'~ sao cho:

~x_i' = \frac{x_i'}{W} \Rightarrow x_i=Wx_i'~

~a_i' = Wa_i \Rightarrow a_i = \frac{a_i'}{W}~

~b_i' = Wb_i \Rightarrow b_i = \frac{b_i'}{W}~

~\sum_{i=1}^{n} x_i=W \Leftrightarrow \sum_{i=1}^{n} Wx_i'=W \Leftrightarrow \sum_{i=1}^{n} x_i'=1~

~\sum_{i=1}^{n}a_ix_i = \sum_{i=1}^{n}a_i'x_i'~

~\sum_{i=1}^{n}b_ix_i = \sum_{i=1}^{n}b_i'x_i'~

Ta gán lại các biến để khử biến ~W~:

~x_i := x_i'~

~a_i := a_i'~

~b_i := b_i'~

Gọi:

~\alpha = \sum_{i=1}^{n}a_ix_i~

~\beta = \sum_{i=1}^{n}b_ix_i~

Mà ~\sum x_i=1~ thì ta có nhận xét nếu xem cặp số ~(a_i, b_i)~ như một điểm trên hệ tọa độ ~2~ chiều, thì cặp số ~(\alpha, \beta)~ sẽ là một điểm nằm trong/trên bao lồi tạo bởi ~n~ điểm trên. Theo nhận xét này, ta có thể bỏ qua giá trị chính xác của mảng ~x~.

~\alpha\times \beta~ lớn nhất khi ~(\alpha, \beta)~ nằm trên bao lồi, cũng có nghĩa là kết quả sẽ nằm trên ~1~ cạnh của tập điểm ~(a_i, b_i)~ hoặc nằm hẳn trên ~1~ điểm của tập điểm.

Vậy ta xét đồ thị đầy đủ đúng ~n^2~ cạnh (có cạnh từ một đỉnh đến chính nó), mỗi cạnh ~(u; v)~ sẽ có trọng số là ~\alpha\times \beta~ lớn nhất sao cho ~(\alpha, \beta)~ nằm trên đoạn thẳng ~\left[(a_u, b_u); (a_v, b_v)\right]~. Tìm ~2~ cạnh không có đỉnh chung sao cho tổng trọng số là lớn nhất. Đó sẽ là kết quả ~V~ cần tìm.

Để tìm được giá trị lớn nhất của ~\alpha \times \beta~ với điểm ~C = (\alpha, \beta)~ là một điểm nằm trên đoạn thẳng nối từ điểm ~A = (x_A, y_A)~ đến điểm ~B = (x_B, y_B)~. Ta có thể biểu diễn điểm ~C~ là một hàm số theo ~t~ sao cho:

~C(t) = tA+(1-t)B, \quad t \in [0; 1]~

Từ đó ta có thể xem ~\alpha \times \beta~ là một hàm số ~f~ theo ~t~:

~\begin{align*} f(t)&= \alpha(t) \times \beta(t)\\ &=[tx_A + (1-t)x_B] \times [ty_A + (1-t)y_B]\\ &=[tx_A + x_B - tx_B] \times [ty_A + y_B - ty_B]\\ &=[t(x_A-x_B) + x_B] \times [t(y_A-y_B) + y_B]\\ &=t^2 (x_A - x_B)(y_A - y_B) + t[y_B(x_A - x_B) + x_B(y_A - y_B)] + x_By_B \end{align*}~

Dễ nhận xét rằng cực đại của ~\alpha(t)\times\beta(t)~ có thể đạt tại các điểm ~t \in \{0;1;t_0\}~ với ~t_0~ là nghiệm của đạo hàm của ~f~.

~t_0=\frac{y_B(x_B - x_A) + x_B(y_B - y_A)}{2(x_A - x_B)(y_A - y_B)}=\frac{y_B}{2(y_B - y_A)}+\frac{x_B}{2(x_B - x_A)}~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const long double MIN_SUM_VALUE = LLONG_MIN; 

struct Candidate { 
    double value; 
    int i; 
    int j; 
    Candidate(double _value, int _i, int _j) : value(_value), i(_i), j(_j) { 
        // cout << "candidate: " <<  i << " " << j << endl; 
    }

    bool operator < (const Candidate &o) const { 
        return value < o.value; 
    }
}; 

vector<pair<int, int> > input() { 
    int n, w; 
    cin >> n >> w; 
    vector<pair<int, int> > pts = vector<pair<int, int> > (n); 
    for(int i = 0; i < n; i++) { 
        cin >> pts[i].first;
        pts[i].first *= w; 
    }
    for(int i = 0;i < n; i++) {
        cin >> pts[i].second; 
        pts[i].second *= w; 
    }
    return pts; 
}


void output(double ans) { 
    cout << fixed << setprecision(10) << ans << endl; 
}


double get_max_area(const pair<int, int> &A, const pair<int, int> &B) { 
    double re = max(A.first * A.second, B.first * B.second); 

    double c0 = 2.0 * (A.first - B.first) * (A.second - B.second); 
    double c1 = 1.0 * (B.second * (A.first - B.first) + B.first * (A.second - B.second)); 

    if(abs(c0) > 1e-6) { 
        double t = -c1 / c0; 
        if(0 <= t && t <= 1) {
            pair<double, double> opt (t * A.first + (1 - t) * B.first, t * A.second + (1 - t) * B.second); 
            re = max(re, opt.first * opt.second); 
        }
    }

    return re; 
}

bool clash(const Candidate &x, const Candidate& y) { 
    return x.i == y.i || x.i == y.j || x.j == y.i || x.j == y.j; 
}

double solve(const vector<pair<int, int> > & _pts) { 
    vector<pair<int, int> > pts = _pts; 
    vector<Candidate> candidates; 
    int n = pts.size(); 
    for(int i = 0; i < n; i++) { 
        for(int j = i; j < n; j++) { //from i to n, not from i + 1 to n. 
            candidates.push_back(Candidate(get_max_area(pts[i], pts[j]), i, j)); 
        }
    }
    sort(begin(candidates), end(candidates)); 
    reverse(begin(candidates), end(candidates)); 

    // search from 4 * n maximum candidates
    int num_search = min(4 * n, (int) candidates.size()); 
    double max_sum = MIN_SUM_VALUE; 

    for(int i = 0; i < num_search; i++) { 
        for(int j = i + 1; j < num_search; j++) { 
            if(!clash(candidates[i], candidates[j])) { 
                // cout << "not clash: " << candidates[i].i << " " << candidates[i].j << " " << candidates[j].i << " " << candidates[j].j << endl; 
                max_sum = max(max_sum, candidates[i].value + candidates[j].value); 
            }
        }
    }

    return max_sum; 
}

void run_problem() { 
    vector<pair<int, int > > pts = input(); 
    double max_ans = solve(pts); 
    output(max_ans); 
}

void test() { 
}

int main() {
    run_problem(); 
}