시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 1794 339 179 15.757%

문제

평면 위에 N개의 점이 주어졌을 때, 가장 큰 정사각형의 넓이를 구하여라.

입력

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

각 테스트케이스의 첫째 줄에는 점의 개수 N(4 ≤ n ≤ 3,000)이 주어지고, 이어서 N개의 줄에는 점의 x좌표와 y좌표가 주어진다. 모든 좌표는 -10000 이상 +10000이하의 정수이다.

출력

가장 큰 정사각형의 넓이를 출력한다.

단, 정사각형이 없는 경우 0을 출력한다.

예제 입력 1

1
10
5 2
10 2
7 4
2 5
8 5
5 7
6 7
10 7
8 9
3 10

예제 출력 1

26
W3sicHJvYmxlbV9pZCI6IjkwMTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNjOVx1YmE3NCBcdWM3MDRcdWM1ZDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvc3F1YXJlLnBuZ1wiIHN0eWxlPVwiZm9udC1zaXplOm1lZGl1bTsgaGVpZ2h0OjE5NXB4OyB0ZXh0LWFsaWduOmNlbnRlcjsgd2lkdGg6MTkycHhcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTig0ICZsZTsgbiAmbGU7IDMsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsJm5ic3A7XHVjNzc0XHVjNWI0XHVjMTFjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCB4XHVjODhjXHVkNDVjXHVjNjQwIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1YmFhOFx1YjRlMCBcdWM4OGNcdWQ0NWNcdWIyOTQmbmJzcDstMTAwMDAgXHVjNzc0XHVjMGMxJm5ic3A7KzEwMDAwXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDBcdWM3YTUgXHVkMDcwIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTgsIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwIDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkwMTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTcXVhcmUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZXJlIGFyZSBuIHBvaW50cyBpbiB0aGUgcGxhbmU8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoIGZpbmRzIGEgbGFyZ2VzdCBzcXVhcmUgc3VjaCB0aGF0IGVhY2ggb2YgaXRzIHZlcnRpY2VzIGlzIG9uZSBvZiB0aGUgZ2l2ZW4gcG9pbnRzIGFuZCBpdHMgYXJlYSBpcyBncmVhdGVyIHRoYW4gMC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvc3F1YXJlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5NXB4OyB3aWR0aDoxOTJweFwiIFwvPjxcL3A+XHJcbiIsImlucHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHJlYWQgZnJvbSBzdGFuZGFyZCBpbnB1dC4gVGhlIGlucHV0IGNvbnNpc3RzIG9mIFQgdGVzdCBjYXNlcy4gVGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzIFQgaXMgZ2l2ZW4gaW4gdGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSBzdGFydHMgd2l0aCBhbiBpbnRlZ2VyIG4sIHRoZSBudW1iZXIgb2YgcG9pbnRzLCB3aGVyZSA0ICZsZTsgbiAmbGU7IDMsMDAwLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMsIHJlcHJlc2VudGluZyB4LWNvb3JkaW5hdGUgYW5kIHktY29vcmRpbmF0ZSBvZiB0aGUgcG9pbnRzIGJldHdlZW4gLTEwPHN1cD40PFwvc3VwPiBhbmQgKzEwPHN1cD40PFwvc3VwPiwgaW5jbHVzaXZlbHkuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIGFuIGludGVnZXIsIHRoZSBhcmVhIG9mIGEgbGFyZ2VzdCBzcXVhcmUuIElmIHRoZXJlIGlzIG5vIHNxdWFyZSwgcHJpbnQgb3V0IDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d