시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB179915049.020%

문제

상근이는 선영이의 채소를 훔친다. 선영이는 이를 막기위해 모든 채소를 울타리로 보호하려고 한다. 선영이는 최대한 값싸게(짧게) 울타리를 만들려고 한다. 알 수 없는 이유로 인해서 울타리는 직사각형 모양으로만 칠 수 있다.

모든 채소는 크기를 무시할 수 있으며, 이차원 평면 위의 점으로 나타낸다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채소의 수 N (3 ≤ N ≤ 10 000) 이 주어진다.다음 N개 줄에는 채소의 좌표를 나타내는 두 정수 Xi 와 Yi (0 ≤ Xi, Yi ≤ 10 000) 가 주어진다. 두 채소가 같은 좌표를 갖는 경우는 없다. 입력으로 주어지는 모든 채소가 한 직선 위에 있는 경우는 없다.

출력

각 테스트 케이스마다 울타리의 둘레 t를 출력한다. 울타리의 변은 축에 평행하지 않아도 된다.

정답과의 차이는 0.0005까지 허용된다.

예제 입력 1

3
0 0
1 0
0 1
3
10 0
0 10
4 4
4
1 0
0 1
2 1
1 2

예제 출력 1

4
31.112698
5.656854
W3sicHJvYmxlbV9pZCI6IjkyNzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjNDRcdWMxOGMgXHViY2Y0XHVkNjM4IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMTIwXHVjNjAxXHVjNzc0XHVjNzU4IFx1Y2M0NFx1YzE4Y1x1Yjk3YyBcdWQ2ZDRcdWNlNWNcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM3NzRcdWI5N2MgXHViOWM5XHVhZTMwXHVjNzA0XHVkNTc0IFx1YmFhOFx1YjRlMCBcdWNjNDRcdWMxOGNcdWI5N2MgXHVjNmI4XHVkMGMwXHViOWFjXHViODVjIFx1YmNmNFx1ZDYzOFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzEyMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVhYzEyXHVjMmY4XHVhYzhjKFx1YzllN1x1YWM4YykgXHVjNmI4XHVkMGMwXHViOWFjXHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzU0YyBcdWMyMTggXHVjNWM2XHViMjk0IFx1Yzc3NFx1YzcyMFx1Yjg1YyBcdWM3NzhcdWQ1NzRcdWMxMWMgXHVjNmI4XHVkMGMwXHViOWFjXHViMjk0IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWJhYThcdWM1OTFcdWM3M2NcdWI4NWNcdWI5Y2MgXHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWNjNDRcdWMxOGNcdWIyOTQgXHVkMDZjXHVhZTMwXHViOTdjIFx1YmIzNFx1YzJkY1x1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3NzRcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M0NFx1YzE4Y1x1Yzc1OCBcdWMyMTgmbmJzcDtOICgzICZsZTsgTiAmbGU7IDEwIDAwMCkgXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzQ0XHVjMThjXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCZuYnNwO1g8c3ViPmk8XC9zdWI+IFx1YzY0MCBZPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IFg8c3ViPmk8XC9zdWI+LCBZPHN1Yj5pPFwvc3ViPiAmbGU7IDEwIDAwMCkgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDUwIFx1Y2M0NFx1YzE4Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMxNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWNjNDRcdWMxOGNcdWFjMDAgXHVkNTVjIFx1YzljMVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNmI4XHVkMGMwXHViOWFjXHVjNzU4Jm5ic3A7XHViNDU4XHViODA4IHRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM2YjhcdWQwYzBcdWI5YWNcdWM3NTggXHViY2MwXHVjNzQwIFx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNTQ0XHViM2M0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODE1XHViMmY1XHVhY2ZjXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YjI5NCAwLjAwMDVcdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjkyNzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGZW5jZSBPcnRob2dvbmFsaXR5IiwiZGVzY3JpcHRpb24iOiI8cD5FdmlsIGJ1bm5pZXMgYXJlIGVhdGluZyBGcmVkZHkmcnNxdW87cyB2ZWdldGFibGVzLiBJbiBvcmRlciB0byBzdG9wIHRoZW0sIGhlIGRlY2lkZWQgdG8gYnVpbGQgYSBmZW5jZSBlbmNsb3NpbmcgYWxsIHZlZ2V0YWJsZXMgaW4gaGlzIGdhcmRlbi4gRnJlZGR5IHdhbnRzIHRoZSBmZW5jZSB0byBiZSBhcyBjaGVhcCAoaS5lLiwgc2hvcnQpIGFzIHBvc3NpYmxlLCBidXQgZm9yIHRlY2huaWNhbCByZWFzb25zLCBoZSBjYW4gb25seSBidWlsZCByZWN0YW5ndWxhciBmZW5jZXMuIEZvciBzaW1wbGljaXR5LCB3ZSB3aWxsIGFzc3VtZSB0aGUgdmVnZXRhYmxlcyBhcmUgbmVnbGlnaWJseSBzbWFsbCBhbmQgY2FuIGJlIHJlcHJlc2VudGVkIGJ5IHBvaW50cyBpbiBhIHR3by1kaW1lbnNpb25hbCBwbGFuZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIFRoZSBcdWZiMDFyc3QgbGluZSBvZiBlYWNoIHRlc3QgY2FzZSBjb250YWlucyBvbmUgaW50ZWdlciBOICgzICZsZTsgTiAmbGU7IDEwIDAwMCkgZ2l2aW5nIHRoZSBudW1iZXIgb2YgdmVnZXRhYmxlcyBpbiB0aGUgZ2FyZGVuLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyB0d28gaW50ZWdlcnMgWDxzdWI+aTxcL3N1Yj4gYW5kIFk8c3ViPmk8XC9zdWI+ICgwICZsZTsgWDxzdWI+aTxcL3N1Yj4sIFk8c3ViPmk8XC9zdWI+ICZsZTsgMTAgMDAwKSwgZ2l2aW5nIHRoZSBjb29yZGluYXRlcyBvZiBvbmUgdmVnZXRhYmxlIHRvIGJlIHByb3RlY3RlZC4gTm8gdHdvIHZlZ2V0YWJsZXMgaGF2ZSB0aGUgc2FtZSBjb29yZGluYXRlcy4gWW91IG1heSBhbHNvIGFzc3VtZSB0aGUgdmVnZXRhYmxlcyBhcmUgbm90IGFsbCBvbiB0aGUgc2FtZSBzdHJhaWdodCBsaW5lLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBvbmUgcmVhbCBudW1iZXIgdCwgZ2l2aW5nIHRoZSBzbWFsbGVzdCBsZW5ndGggb2YgdGhlIHBlcmltZXRlciBvZiBhIHJlY3Rhbmd1bGFyIGZlbmNlIGVuY2xvc2luZyBhbGwgdGhlIHZlZ2V0YWJsZXMuIE5vdGUgdGhhdCB0aGUgZWRnZXMgb2YgdGhlIHJlY3RhbmdsZSBkbyBub3QgbmVlZCB0byBiZSBwYXJhbGxlbCB3aXRoIHRoZSBjb29yZGluYXRlIGF4ZXMuPFwvcD5cclxuXHJcbjxwPlRoZSBhbnN3ZXIgd2lsbCBiZSBhY2NlcHRlZCBhcyBjb3JyZWN0IGlmIHRoZSBkaVx1ZmIwMGVyZW5jZSBiZXR3ZWVuIHQgYW5kIHRoZSBleGFjdCBhbnN3ZXIgaXMgYXQgbW9zdCAwLjAwMDUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest 2013 O번