시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 256 MB 164 42 29 26.364%

문제

레프의 부대는 전장에 새 기지를 짓고, 여러 직선 벽으로 구성된 요새와 감시탑으로 이를 둘러싸기로 했다. 두 벽이 만나는 점에는 반드시 감시탑을 설치해야 하고, 전시에 조직적인 움직임을 위해 감시탑은 최대 4개까지만 설치하기로 했다

꼼꼼한 조사 끝에 레프는 탑의 무게를 견딜 수 있고, 시야 확보가 가능한 몇 군데의 점이 감시탑 설치에 적합하다고 판단했다.

프로그래밍을 배운 적이 없는 레프는 가장 넓은 기지를 짓기 위해 여러분에게 가능한 가장 넓은 기지의 넓이를 출력하는 프로그램을 짜  줄 것을 부탁했다. 하지만 정확한 위치는 군사 기밀이기 때문에, 위치는 입력으로만 주어지고, 또한 여러 가짜 데이터 속에 진짜 데이터를 숨길 수 있도록 많은 테스트 케이스를 다룰 수 있어야 한다는 조건을 추가했다. 레프를 만족하게 할 프로그램을 작성해 보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1≤T≤100)가 주어진다.

각각의 테스트 케이스에 대해, 테스트 케이스의 첫 줄에는 감시탑 건설에 적합한 위치의 수 n (3 ≤ n ≤ 1,000)이 주어지며, 이후 n개의 줄에는 감시탑 건설에 적합한 n개의 위치의 x, y좌표가 공백을 사이에 두고 주어진다. 모든 위치의 좌푯값은 모두 다르다.(-10,000 ≤ x, y ≤ 10,000)

출력

각각의 테스트 케이스에 대해, 한 줄에 기지의 최대 넓이를 출력한다. 기지의 넓이가 반정수일 경우 "정수.5"의 형식으로 출력한다. 2.50000과 같이 뒤에 0을 출력할 경우 오답 처리한다.

예제 입력 1

3
6
0 0
3 7
10 0
11 6
0 10
10 10
5
0 0
-2 -2
3 -2
0 1
0 3
10
3 1
4 1
5 9
2 6
5 3
5 8
9 7
9 3
2 3
8 4

예제 출력 1

100
12.5
31
W3sicHJvYmxlbV9pZCI6IjEwMzIxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjNjk0XHVjMGM4IFx1YWM3NFx1YzEyNCIsImRlc2NyaXB0aW9uIjoiPHA+XHViODA4XHVkNTA0XHVjNzU4IFx1YmQ4MFx1YjMwMFx1YjI5NCBcdWM4MDRcdWM3YTVcdWM1ZDAgXHVjMGM4IFx1YWUzMFx1YzljMFx1Yjk3YyBcdWM5ZDNcdWFjZTAsIFx1YzVlY1x1YjdlYyBcdWM5YzFcdWMxMjAgXHViY2JkXHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxYyBcdWM2OTRcdWMwYzhcdWM2NDAgXHVhYzEwXHVjMmRjXHVkMGQxXHVjNzNjXHViODVjIFx1Yzc3NFx1Yjk3YyBcdWI0NThcdWI3ZWNcdWMyZjhcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWI0NTAgXHViY2JkXHVjNzc0IFx1YjljY1x1YjA5OFx1YjI5NCBcdWM4MTBcdWM1ZDBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YWMxMFx1YzJkY1x1ZDBkMVx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWM4MDRcdWMyZGNcdWM1ZDAgXHVjODcwXHVjOWMxXHVjODAxXHVjNzc4IFx1YzZjMFx1YzljMVx1Yzc4NFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVhYzEwXHVjMmRjXHVkMGQxXHVjNzQwIFx1Y2Q1Y1x1YjMwMCA0XHVhYzFjXHVhZTRjXHVjOWMwXHViOWNjIFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQ8XC9wPlxyXG5cclxuPHA+XHVhZjNjXHVhZjNjXHVkNTVjIFx1Yzg3MFx1YzBhYyBcdWIwNWRcdWM1ZDAgXHViODA4XHVkNTA0XHViMjk0IFx1ZDBkMVx1Yzc1OCBcdWJiMzRcdWFjOGNcdWI5N2MgXHVhY2FjXHViNTFjIFx1YzIxOCBcdWM3ODhcdWFjZTAsIFx1YzJkY1x1YzU3YyBcdWQ2NTVcdWJjZjRcdWFjMDAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmE4NyBcdWFkNzBcdWIzNzBcdWM3NTggXHVjODEwXHVjNzc0IFx1YWMxMFx1YzJkY1x1ZDBkMSBcdWMxMjRcdWNlNThcdWM1ZDAgXHVjODAxXHVkNTY5XHVkNTU4XHViMmU0XHVhY2UwIFx1ZDMxMFx1YjJlOFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTA0XHViODVjXHVhZGY4XHViNzk4XHViYzBkXHVjNzQ0IFx1YmMzMFx1YzZiNCBcdWM4MDFcdWM3NzQgXHVjNWM2XHViMjk0IFx1YjgwOFx1ZDUwNFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMTEzXHVjNzQwIFx1YWUzMFx1YzljMFx1Yjk3YyBcdWM5ZDNcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1YzVkMFx1YWM4YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhYzAwXHVjN2E1IFx1YjExM1x1Yzc0MCBcdWFlMzBcdWM5YzBcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjOWRjICZuYnNwO1x1YzkwNCBcdWFjODNcdWM3NDQgXHViZDgwXHVkMGMxXHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjODE1XHVkNjU1XHVkNTVjIFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWFkNzBcdWMwYWMgXHVhZTMwXHViYzAwXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNzA0XHVjZTU4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1Y1x1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjYxMFx1ZDU1YyBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWRjIFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWMxOGRcdWM1ZDAgXHVjOWM0XHVjOWRjIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWMyMjhcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCBcdWI5Y2VcdWM3NDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjk3YyBcdWIyZTRcdWI4ZjAgXHVjMjE4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWIyOTQgXHVjODcwXHVhYzc0XHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU4OFx1YjJlNC4gXHViODA4XHVkNTA0XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YWM4YyBcdWQ1NjAgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU3NCBcdWJjZjRcdWM3OTAuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoMSZsZTtUJmxlOzEwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMTBcdWMyZGNcdWQwZDEgXHVhYzc0XHVjMTI0XHVjNWQwIFx1YzgwMVx1ZDU2OVx1ZDU1YyBcdWM3MDRcdWNlNThcdWM3NTggXHVjMjE4IG4gKDMmbmJzcDsmbGU7Jm5ic3A7biZuYnNwOyZsZTsmbmJzcDsxLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWQ2YzQgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzEwXHVjMmRjXHVkMGQxIFx1YWM3NFx1YzEyNFx1YzVkMCBcdWM4MDFcdWQ1NjlcdWQ1NWMgblx1YWMxY1x1Yzc1OCBcdWM3MDRcdWNlNThcdWM3NTggeCwgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YjQ1MFx1YWNlMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWM3MDRcdWNlNThcdWM3NTggXHVjODhjXHVkNDZmXHVhYzEyXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZTRcdWI5NzRcdWIyZTQuKC0xMCwwMDAmbmJzcDsmbGU7IHgsIHkmbmJzcDsmbGU7IDEwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVhZTMwXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWFlMzBcdWM5YzBcdWM3NTggXHViMTEzXHVjNzc0XHVhYzAwIFx1YmMxOFx1YzgxNVx1YzIxOFx1Yzc3YyBcdWFjYmRcdWM2YjAgJnF1b3Q7XHVjODE1XHVjMjE4LjUmcXVvdDtcdWM3NTggXHVkNjE1XHVjMmRkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gMi41MDAwMFx1YWNmYyBcdWFjMTlcdWM3NzQgXHViNGE0XHVjNWQwIDBcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YWNiZFx1YzZiMCBcdWM2MjRcdWIyZjUgXHVjYzk4XHViOWFjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwMzIxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2l0YWRlbCBDb25zdHJ1Y3Rpb24iLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBhcm15IHdhbnRzIHRvIHB1dCB1cCBhIG5ldyBiYXNlIGluIGRhbmdlcm91cyB0ZXJyaXRvcnkuIFRoZSBiYXNlIHdpbGwgYmUgc3Vycm91bmRlZCBieSBhIGNpdGFkZWwgY29uc2lzdGluZyBvZiBhIG51bWJlciBvZiBzdHJhaWdodCB3YWxscy4gQXQgZXZlcnkgY29ybmVyIHdoZXJlIHR3byB3YWxscyBtZWV0LCB0aGVyZSB3aWxsIGJlIGEgd2F0Y2h0b3dlci4gSW4gb3JkZXIgdG8gZW5hYmxlIGVmZmljaWVudCBjb29yZGluYXRpb24gaW4gY2FzZSBvZiBhdHRhY2ssIHRoZSBudW1iZXIgb2Ygd2F0Y2h0b3dlcnMgc2hvdWxkIG5vdCBleGNlZWQgZm91ci48XC9wPlxyXG5cclxuPHA+PGEgaHJlZj1cImh0dHBzOlwvXC94a2NkLmNvbVwvMTE5MFwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL1RpbWU0MTQucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjM5NXB4OyB3aWR0aDo1NTNweFwiIFwvPjxcL2E+QWZ0ZXIgYSBkZXRhaWxlZCBzdXJ2ZXkgb2YgdGhlIGFyZWEsIHRoZSBhcm15IGhhcyBjb25jbHVkZWQgdGhhdCBub3QgYWxsIGxvY2F0aW9ucyBhcmUgZXF1YWxseSBzdWl0YWJsZSBmb3IgYSB3YXRjaHRvd2VyOiB0aGUgZ3JvdW5kIG5lZWRzIHRvIGJlIGZpcm0gZW5vdWdoIHRvIHN1cHBvcnQgdGhlIHdlaWdodCBvZiB0aGUgdG93ZXIsIGFuZCB0aGVyZSBzaG91bGQgYmUgZW5vdWdoIHZpc2liaWxpdHkuIFRoZXkgaGF2ZSBzZWxlY3RlZCBhIG51bWJlciBvZiBsb2NhdGlvbnMgdGhhdCBtZWV0IHRoZSByZXF1aXJlbWVudHMuPFwvcD5cclxuXHJcbjxwPldpdGhpbiB0aGVzZSBjb25zdHJhaW50cywgdGhlIGFybXkgd291bGQgbGlrZSB0byBidWlsZCBhIGJhc2UgdGhhdCBpcyBhcyBsYXJnZSBhcyBwb3NzaWJsZS4gRm9yIHRoaXMsIHRoZXkgaGF2ZSBjb21lIHRvIHlvdSBmb3IgaGVscC4gU2luY2UgdGhlIHJlc3VsdHMgb2YgdGhlIHN1cnZleSBhcmUgb2YgY291cnNlIGNsYXNzaWZpZWQsIHlvdSB3aWxsIG5vdCBiZSBnaXZlbiB0aGUgcG9zc2libGUgbG9jYXRpb25zIGRpcmVjdGx5OyByYXRoZXIsIHlvdSBzaG91bGQgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FuIHRha2UgdGhlbSBhcyBpbnB1dC4gRnVydGhlcm1vcmUsIHRoZXkgd2FudCB0aGUgcHJvZ3JhbSB0byBiZSBhYmxlIHRvIGhhbmRsZSBtdWx0aXBsZSB0ZXN0IGNhc2VzIGluIG9uZSBnbywgc28gdGhhdCB0aGV5IGNhbiBoaWRlIHRoZSByZWFsIGRhdGEgYW1vbmcgbG90cyBvZiBmYWtlIGRhdGEuPFwvcD5cclxuXHJcbjxwPkZvciB0aGUgY29tcHV0YXRpb24gb2YgdGhlIGFyZWEsIHlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIHdhdGNodG93ZXJzIGFyZSBpbmZpbml0ZXNpbWFsIGluIHNpemUgYW5kIHRoZSB3YWxscyBpbmZpbml0ZXNpbWFsIGluIHdpZHRoLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBuICgzICZsZTsgbiAmbGU7IDEgMDAwKTogdGhlIG51bWJlciBvZiBsb2NhdGlvbnMgdGhhdCBhcmUgc3VpdGFibGUgZm9yIGEgd2F0Y2h0b3dlci48XC9saT5cclxuXHQ8bGk+biBsaW5lcywgZWFjaCB3aXRoIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgeCBhbmQgeSAoJm1pbnVzOzEwIDAwMCAmbGU7IHgsIHkgJmxlOyAxMCAwMDApOiB0aGUgY29vcmRpbmF0ZXMgb2YgZWFjaCBsb2NhdGlvbi48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5BbGwgbG9jYXRpb25zIGFyZSBkaXN0aW5jdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzaW5nbGUgbnVtYmVyOiB0aGUgbGFyZ2VzdCBwb3NzaWJsZSBhcmVhIHRoYXQgdGhlIGJhc2UgY2FuIGhhdmUuIFRoaXMgbnVtYmVyIHdpbGwgYmUgZWl0aGVyIGFuIGludGVnZXIgb3IgYSBoYWxmLWludGVnZXIuIElmIGl0IGlzIGFuIGludGVnZXIsIHByaW50IHRoYXQgaW50ZWdlcjsgaWYgaXQgaXMgYSBoYWxmLWludGVnZXIsIHByaW50IHRoZSBpbnRlZ2VyIHBhcnQgZm9sbG93ZWQgYnkgJmxkcXVvOy41JnJkcXVvOy4gVHJhaWxpbmcgemVyb3MgYXJlIG5vdCBhbGxvd2VkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d