题意简述：给定二维平面上的 $N$ 个点，要求找出欧几里得距离最远的两个点，并输出它们的编号。

最直观的想法是两层 for 循环枚举所有的点对，计算它们之间的距离并取最大值。复杂度是 $O(N^2)$。显然对于 $N = 5 \times 10^5$ 的数据量绝对会超时。

所以我们稍微改进一下思路，不难想到凸包。一个很重要的几何性质是：平面上距离最远的两个点，必定在这个点集的凸包的顶点上。因此我们的第一步是求出这 $N$ 个点的凸包，把无用的内部点全部剔除。这里使用经典的 Andrew 算法：

1. 先将所有点按 $x$ 坐标为主关键字、$y$ 坐标为副关键字从小到大排序；
2. 用一个栈维护凸包的顶点，先从左往右遍历一遍求出下半凸包，再从右往左遍历一遍求出上半凸包。

求凸包的时间复杂度主要在排序上，为 $O(N \log N)$。

如果到这里就结束了还是差了不少。因为得到凸包后哪怕全是凸包上的点，若点全在一个圆上，暴力枚举还是能退化到 $O(N^2)$。

核心思想是利用凸包的单调性，使用双指针在 $O(N)$ 的时间内跑完所有边和对立点。实现如下：

1. 逆时针遍历凸包上的每一条边 $(i, i+1)$；
2. 随着边的逆时针转动，距离这条边最远的顶点 $j$ 也是单调逆时针移动的；
3. 比较叉积来判断点 $j$ 到边 $(i, i+1)$ 的距离。当 $(i, i+1, j+1)$ 的三角形面积大于 $(i, i+1, j)$ 的面积时，说明指针 $j$ 应该继续向前移动；
4. 找到最远点 $j$ 后，最远点对就一定产生在 $(i, j)$ 或者 $(i+1, j)$ 之间，更新全局最大距离即可。

复杂度 $O(N \log N)$。

不过显然坐标值的绝对值可以达到 $10^9$，注意爆 int。

还有一个特殊的点：计算欧几里得距离时，直接比较距离的平方即可，开根号反而有精度损失。

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

template<typename T>
inline void read(T &x) {
    x = 0;
    T f = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
    x *= f;
}

template<typename T>
inline void write(T x, char ec = '\n') {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10, 0);
    putchar(x % 10 + '0');
    if (ec) putchar(ec);
}

struct Pt {
    long long x, y;
    int id;
} p[500005], stk[500005];

inline long long dst(Pt a, Pt b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

inline long long crs(Pt a, Pt b, Pt c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

bool cmp(Pt a, Pt b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

void solve() {
    int n;
    read(n);
    for (int i = 0; i < n; i++) {
        read(p[i].x);
        read(p[i].y);
        p[i].id = i;
    }
    sort(p, p + n, cmp);
    
    int top = 0;
    for (int i = 0; i < n; i++) {
        while (top > 1 && crs(stk[top - 2], stk[top - 1], p[i]) <= 0) top--;
        stk[top++] = p[i];
    }
    int tmp = top;
    for (int i = n - 2; i >= 0; i--) {
        while (top > tmp && crs(stk[top - 2], stk[top - 1], p[i]) <= 0) top--;
        stk[top++] = p[i];
    }
    if (n > 1) top--;

    if (top == 1) {
        write(0, ' ');
        write(1, '\n');
        return;
    }
    if (top == 2) {
        write(stk[0].id, ' ');
        write(stk[1].id, '\n');
        return;
    }

    long long mxd = -1;
    int r1 = 0, r2 = 0;
    for (int i = 0, j = 1; i < top; i++) {
        while (crs(stk[i], stk[(i + 1) % top], stk[(j + 1) % top]) > crs(stk[i], stk[(i + 1) % top], stk[j])) {
            j = (j + 1) % top;
        }
        long long d1 = dst(stk[i], stk[j]);
        if (d1 > mxd) {
            mxd = d1;
            r1 = stk[i].id;
            r2 = stk[j].id;
        }
        long long d2 = dst(stk[(i + 1) % top], stk[j]);
        if (d2 > mxd) {
            mxd = d2;
            r1 = stk[(i + 1) % top].id;
            r2 = stk[j].id;
        }
    }
    write(r1, ' ');
    write(r2, '\n');
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    read(t);
    while (t--) solve();
    return 0;
}