시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2691 269 123 15.111%

문제

n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다.

고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 중 유클리드 거리가 가장 먼 두 도시를 찾으려 한다. 모든 도시는 한 평면 위에 있다.

위의 예제에서는 (12,0)의 도시와 (-6,3)의 도시가 가장 먼 유클리드 거리를 갖는다.

도시 n개의 좌표가 주어지면 모든 두 도시 쌍의 거리 중 가장 먼 두 도시를 찾아라.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 

각 테스트 케이스의 첫 줄엔 도시의 개수 n이 주어진다. (2 ≤ n ≤ 200,000그 후 n줄에 걸쳐 각 도시의 x좌표와 y좌표가 주어진다. (-10,000,000 ≤ x, y ≤ 10,000,000) x, y는 항상 정수이며, 어떤 두 도시가 같은 점 위에 있는 경우는 없다.

출력

테스트 케이스마다 가장 먼 두 점의 좌표를 출력한다.

만일 그 두 점의 좌표가 각각 (x1, y1), (x2, y2)이라면 x1 y1 x2 y2를 출력하면 된다.

가장 먼 거리를 갖는 두 점의 쌍이 여러 개라면 그 중 아무 것이나 출력해도 상관없다.

예제 입력 1

2
4
-100 -50
20 -50
-20 50
100 50
9 
-1 -1
3 -3 
6 -6 
-3 -6 
12 0
3 4
-6 3
0 9
6 9

예제 출력 1

-100 -50 100 50
-6 3 12 0
W3sicHJvYmxlbV9pZCI6IjEwMjU0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2UwXHVjMThkXHViM2M0XHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5uXHVhYzFjXHVjNzU4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWFjMDBcdWM5YzQgXHViMDk4XHViNzdjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1YzVkMFx1YzExY1x1YjI5NCBcdWIzYzRcdWMyZGNcdWI0ZTQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDAgXHVjOWMxXHVkNTg5IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWIxOTNcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWIyOTQgXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjA1ZFx1YzgxMFx1Yzc3NCBcdWM1NDRcdWIyY2MgXHViMmU0XHViOTc4IFx1YjA5OFx1Yjc3Y1x1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWM5ODksIG5cdWFjMWNcdWM3NTggXHViM2M0XHVjMmRjIFx1YzkxMSBcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzcwXHViOWFjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViMjk0IFx1ZDU1YyBcdWQzYzlcdWJhNzQgXHVjNzA0XHVjNWQwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBzcmM9XCJodHRwczpcL1wvd3d3LmFjbWljcGMubmV0XC91cGxvYWRcL2ltYWdlczJcL2hpZ2h3YXkoMSkucG5nXCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWNcdWIyOTQgKDEyLDApXHVjNzU4IFx1YjNjNFx1YzJkY1x1YzY0MCAoLTYsMylcdWM3NTggXHViM2M0XHVjMmRjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWJhM2MgXHVjNzIwXHVkMDc0XHViOWFjXHViNGRjIFx1YWM3MFx1YjlhY1x1Yjk3YyBcdWFjMTZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjNjNFx1YzJkYyBuXHVhYzFjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHViYWE4XHViNGUwIFx1YjQ1MCBcdWIzYzRcdWMyZGMgXHVjMzBkXHVjNzU4IFx1YWM3MFx1YjlhYyBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1YmEzYyBcdWI0NTAgXHViM2M0XHVjMmRjXHViOTdjIFx1Y2MzZVx1YzU0NFx1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMTggVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWIgXHVjOTA0XHVjNWQ0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWFjMWNcdWMyMTggblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4yICZsZTsgbiAmbGU7IDIwMCwwMDA8XC9zcGFuPjxzcGFuIHN0eWxlPVwibGluZS1oZWlnaHQ6MS42ZW1cIj4pJm5ic3A7PFwvc3Bhbj48c3BhbiBzdHlsZT1cImxpbmUtaGVpZ2h0OjEuNmVtXCI+XHVhZGY4IFx1ZDZjNCBuXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWFjMDEgXHViM2M0XHVjMmRjXHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWM2NDAgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAsMDAwLDAwMCAmbGU7IHgsIHkgJmxlOyAxMCwwMDAsMDAwKSZuYnNwOzxcL3NwYW4+PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPngsIHlcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCwgXHVjNWI0XHViNWE0IFx1YjQ1MCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1YzgxMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YWMwMFx1YzdhNSBcdWJhM2MgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM3N2MgXHVhZGY4IFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YWMwMVx1YWMwMSAoeDEsIHkxKSwgKHgyLCB5MilcdWM3NzRcdWI3N2NcdWJhNzQgeDEgeTEgeDIgeTJcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1YmEzYyBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhYzE2XHViMjk0IFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVjMzBkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI3N2NcdWJhNzQgXHVhZGY4IFx1YzkxMSBcdWM1NDRcdWJiMzQgXHVhYzgzXHVjNzc0XHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTAyNTQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIaWdod2F5IiwiZGVzY3JpcHRpb24iOiI8cD5UaGVyZSBpcyBhIGNvdW50cnkgdGhhdCBoYXMgbiBjaXRpZXMuIFRoZSBjb3VudHJ5IGRlY2lkZXMgdG8gYnVpbGQgdGhlIGxvbmdlc3Qgc3RyYWlnaHQgaGlnaHdheSBjb25uZWN0aW5nIHR3byBjaXRpZXMuIFRoZSBoaWdod2F5IG1heSBwYXNzIHRocm91Z2ggc29tZSBjaXRpZXMuIFRoYXQgaXMsIHRoZXkgd2FudCB0byBmaW5kIHR3byBjaXRpZXMgdGhhdCBoYXZlIG1heGltdW0gRXVjbGlkZWFuIGRpc3RhbmNlIG92ZXIgYWxsIHBhaXJzIG9mIHRoZSBjaXRpZXMuIFRoZSBsb2NhdGlvbiBvZiB0aGUgY2l0aWVzIGlzIGdpdmVuIGJ5IHRoZSBpbnRlZ3JhbCBjb29yZGluYXRlcyBvZiAyLWRpbWVuc2lvbmFsIHBsYW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Gb3IgdGhlIGNhc2Ugb2YgZm9sbG93aW5nIGV4YW1wbGUsIHRoZSB0d28gY2l0aWVzIGxvY2F0ZWQgaW4gKDEyLDApIGFuZCAoLTYsMykgYXJlIHRoZSBwYWlycyB0aGF0IGhhcyBtYXhpbXVtIEV1Y2xpZGVhbiBkaXN0YW5jZS4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2hpZ2h3YXkoMSkucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjY3cHg7IHdpZHRoOjM0N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5GaWd1cmUgMS4gQW4gZXhhbXBsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGZpbmQgdGhlIGxvY2F0aW9uIG9mIHR3byBjaXRpZXMgd2l0aCB0aGUgbWF4aW11bSBFdWNsaWRlYW4gZGlzdGFuY2UuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGFuIGludGVnZXIgbiwgdGhlIG51bWJlciBvZiBjaXRpZXMgb2YgdGhlIGNvdW50cnksIHdoZXJlIDIgJmxlOyBuICZsZTsgMjAwLDAwMC4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgYSBwYWlyIG9mIGludGVnZXJzIHggYW5kIHksIHJlcHJlc2VudGluZyB0aGUgY29vcmRpbmF0ZSBvZiBhIGNpdHkuIE5vdGUgdGhhdCBhbGwgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBjaXRpZXMgYXJlIGRpc3RpbmN0LCBhbmQgLTEwLDAwMCwwMDAgJmxlOyB4LCB5ICZsZTsgMTAsMDAwLDAwMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gd3JpdGUgdG8gc3RhbmRhcmQgb3V0cHV0LiBQcmludCBleGFjdGx5IG9uZSBsaW5lIGZvciBlYWNoIHRlc3QgY2FzZS4gVGhlIGxpbmUgc2hvdWxkIGNvbnRhaW4gZm91ciBpbnRlZ2VycyB4MSwgeTEsIHgyLCBhbmQgeTIgdGhhdCByZXByZXNlbnQgdHdvIGNpdHkgY29vcmRpbmF0ZXMgKHgxLCB5MSkgYW5kICh4MiwgeTIpLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCB0d28gY2l0aWVzLCBhbnkgb25lIG9mIHRoZW0gd2lsbCBiZSBhY2NlcHRlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Asia > Korea > Nationwide Internet Competition > Asia Regional - Daejeon Nationalwide Internet Competition 2014 E번