$\texttt{Subtask 1}$：

暴力即可，时间复杂度 $O(n^2)$。

$\texttt{Subtask 2}$：

可以使用稀疏表或者一些其他排序后再求解的方法，时间复杂度 $O(n\text{log}n)$。

$\texttt{Subtask 3}$：

时间复杂度 $O(n)$。

考虑将每个二元组的 $\texttt{Y}$ 轴坐标取其绝对值，然后将二元组按照 $\texttt{X}$ 坐标递增的顺序进行排列，则两个二元组之间的变异距离可以看成以二元组 $\texttt{X}$ 坐标之间的线段和第一个二元组组 $\texttt{Y}$ 轴坐标所形成的线段、第二个二元组 $\texttt{Y}$ 轴坐标所形成的线段围成的矩形的面积。不过，此矩形的侧边长度是两个二元组 $\texttt{Y}$ 坐标绝对值中的较小值。

根据木桶原理，一个木桶所能装的水的容量只由高度最短的那块木板的决定，而此题中，矩形的面积只由高度较短的线段决定。因此可以考虑用双指针从首尾往中间扫描，在扫描过程中，只移动较短线段的指针，因为矩形的面积取决于较短的线段，只有在改变较短线段的时候才有可能产生新的最大值。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000010;

const int LENGTH = (1 << 20);

inline int nextChar()
{
    static char buffer[LENGTH], *p = buffer, *end = buffer;
    if (p == end) {
        if ((end = buffer + fread(buffer, 1, LENGTH, stdin)) == buffer) return EOF;
        p = buffer;
    }
    return *p++;
}

inline bool nextInt(int &x)
{
    static char negative = 0, c = nextChar();
    negative = 0, x = 0;
    while ((c < '0' || c > '9') && c != '-')
    { if (c == EOF) return false; c = nextChar(); }
    if (c == '-') { negative = 1; c = nextChar(); }
    do x = (x << 3) + (x << 1) + c - '0'; while ((c = nextChar()) >= '0');
    if (negative) x = -x;
    return true;
}

int ps[MAXN];

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    
    int T, n;
    nextInt(T);
    for (int cs = 1; cs <= T; cs++)
    {
        nextInt(n);
        memset(ps, 0, sizeof ps);
        int bias = 1000000;
        for (int i = 0, x, y; i < n; i++)
        {
            nextInt(x);
            nextInt(y);
            ps[x + bias] = max(ps[x + bias], abs(y));
        }
        int low = 0, high = MAXN - 1;
        long long D = 0;
        while (low < high)
        {
            D = max(D, 1LL * abs(low - high) * min(ps[low], ps[high]));
            if (ps[low] <= ps[high]) low++;
            else high--;
        }
        cout << D << '\n';
    }
    return 0;
}