SP3645 HEADQRT - Farthest Headquarters

Microhoo 和 Googloo 是来自同一城市的两家 IT 公司，彼此竞争激烈。它们在城市中各自分布有多个办公室。为了保护公司的重要信息不被对方获取，两家公司计划将各自的总部放在尽可能远的地方。 给出两个公司现有的办公室位置，你需要编写一个程序，帮助他们从这些办公室中选择各自的总部，使它们之间的距离尽可能远。

输入包含多个数据集。第一行是一个正整数，指示数据集的数量，最多为 20。接下来是每个数据集的详细信息。 对于每个数据集，第一行有一个整数 $n$，表示两家公司办公室的总数，有 $2 \le n \le 30000$。接下来的 $n$ 行中，每行有三个整数 $x_i, y_i, c_i$，用空格分隔，表示第 $i$ 个办公室的坐标 $(x_i, y_i)$。如果 $c_i = 0$，则该办公室属于 Microhoo，如果 $c_i = 1$，则属于 Googloo。 保证每家公司至少有一个办公室。

对于每个数据集，输出 Microhoo 和 Googloo 的总部之间的最长距离，取其整数部分。 **本翻译由 AI 自动生成**