BOJ_10254

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

struct Point {
	double x, y;
};
struct d_p {
	int p, q;
	double d;
};
double distance(double x1, double y1, double x2, double y2)
{
	return sqrt(pow(x2 - x1, 2.) + pow(y2 - y1, 2.));
}
double cross(const Point &O, const Point &A, const Point &B)
{
	return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}
vector<Point> convex_hull(vector<Point> P)
{
	int n = P.size(), k = 0;
	vector<Point> H(2 * n);
	sort(P.begin(), P.end(), [](Point p, Point q) { if (p.y == q.y) return p.x < q.x; else return p.y > q.y; });
	for (int i = 0; i < n; ++i) {
		while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}
	for (int i = n - 2, t = k + 1; i >= 0; i--) {
		while (k >= t && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}
	H.resize(k);
	return H;
}
int main()
{
	int number;
	std::cin >> number;
	for (int i = 0; i < number; i++)
	{
		int max_number;
		std::cin >> max_number;
		std::vector <Point> vector;
		for (int vertex = 0; vertex < max_number; vertex++)
		{
			int x, y;
			std::cin >> x >> y;
			vector.push_back({ x, y });
		}
		vector = convex_hull(vector);
		std::vector <d_p> vec(vector.size() + 1);
		int count = 1, max_count = 1;
		for (int i = 0; i < vector.size() - 1; i++)
		{
			double max = 0, temp = 0;
			while (max < (temp = distance(vector[i].x, vector[i].y , vector[count].x, vector[count].y)))
			{
				max = temp;
				max_count = count;
				count++;
				if (count > vector.size() - 1)
					break;
			}
			vec[i] = { i, max_count,max };
			count--;
		}
		sort(vec.begin(), vec.end(), [](d_p a, d_p b) { return a.d > b.d; });
		std::cout << vector[vec[0].p].x << " " << vector[vec[0].p].y << " " << vector[vec[0].q].x << " " << vector[vec[0].q].y << std::endl;
	}
}