시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2 1 1 100.000%

문제

[0, 1]×[0, 1]의 정사각형과 그 안(정사각형의 테두리 및 꼭짓점 포함)에 N개의 점들 P[1], P[2], …, P[N]이 있다. 이 점들과 정사각형의 네 꼭짓점을 연결하여 임의의 두 점이 직접 혹은 간접적으로 연결되어 있게 하려 한다. 이와 같이 만든 그래프의 간선의 길이를 합한 것을 Len(P) 라고 정의하자.

N개의 점들의 위치를 임의로 바꾸면 Len(P)의 값도 이에 따라 변하게 된다. Len(P)가 최소가 되도록 하는 점들의 집합을 P'라고 하자. 즉, Len을 점들의 집합 P에 대한 함수로 생각했을 때, Len의 최솟값이 Len(P')가 되는 것이다.

N개의 점들을 잘 배치하여 Len이 최소가 되도록 할 때, 각각의 점들을 이동시킨 거리가 최소가 되도록 하는 프로그램을 작성하시오.

즉, Len(P'')=Len(P')를 만족하는 P''들 중에서, |P[1]-P''[1]|+|P[2]-P''[2]|+…+|P[N]-P''[N]|이 최소가 될 때, 그 최솟값을 구하는 것이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에 N(1≤N≤100)이 주어진다. 다음 N개의 줄에는 각 점의 x, y 좌표가 주어진다. N이 0인 경우에 프로그램을 종료한다.

출력

각 테스트 케이스마다 답을 출력한다. 절대/상대 오차는 10-3까지 허용한다.

예제 입력 1

1
0.2 0.5
2
0 0.5
0.5 0.5
0

예제 출력 1

0.300
0.500

힌트

 

W3sicHJvYmxlbV9pZCI6IjIyODAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWFjZmMgXHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5bMCwgMV0mdGltZXM7WzAsIDFdXHVjNzU4IFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1YWNmYyBcdWFkZjggXHVjNTQ4KFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc1OCBcdWQxNGNcdWI0NTBcdWI5YWMgXHViYzBmIFx1YWYyZFx1YzlkM1x1YzgxMCBcdWQzZWNcdWQ1NjgpXHVjNWQwIE5cdWFjMWNcdWM3NTggXHVjODEwXHViNGU0IFBbMV0sIFBbMl0sICZoZWxsaXA7LCBQW05dXHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzgxMFx1YjRlNFx1YWNmYyBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHViMTI0IFx1YWYyZFx1YzlkM1x1YzgxMFx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWM1ZWMgXHVjNzg0XHVjNzU4XHVjNzU4IFx1YjQ1MCBcdWM4MTBcdWM3NzQgXHVjOWMxXHVjODExIFx1ZDYzOVx1Yzc0MCBcdWFjMDRcdWM4MTFcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWM4YyBcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LiBcdWM3NzRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YjljY1x1YjRlMCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHVhYzA0XHVjMTIwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWQ1NjlcdWQ1NWMgXHVhYzgzXHVjNzQ0IExlbihQKSBcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzgxMFx1YjRlNFx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjNzg0XHVjNzU4XHViODVjIFx1YmMxNFx1YWZiOFx1YmE3NCBMZW4oUClcdWM3NTggXHVhYzEyXHViM2M0IFx1Yzc3NFx1YzVkMCBcdWI1MzBcdWI3N2MgXHViY2MwXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gTGVuKFApXHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MThcdWIzYzRcdWI4NWQgXHVkNTU4XHViMjk0IFx1YzgxMFx1YjRlNFx1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgUCYjMzk7XHViNzdjXHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjOTg5LCBMZW5cdWM3NDQgXHVjODEwXHViNGU0XHVjNzU4IFx1YzlkMVx1ZDU2OSBQXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWQ1NjhcdWMyMThcdWI4NWMgXHVjMGRkXHVhYzAxXHVkNTg4XHVjNzQ0IFx1YjU0YywgTGVuXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc3NCBMZW4oUCYjMzk7KVx1YWMwMCBcdWI0MThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhYzFjXHVjNzU4IFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWM3OTggXHViYzMwXHVjZTU4XHVkNTU4XHVjNWVjIExlblx1Yzc3NCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU2MCBcdWI1NGMsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWM4MTBcdWI0ZTRcdWM3NDQgXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE4IFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNkNWNcdWMxOGNcdWFjMDAgXHViNDE4XHViM2M0XHViODVkIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM5ODksIExlbihQJiMzOTsmIzM5Oyk9TGVuKFAmIzM5OylcdWI5N2MgXHViOWNjXHVjODcxXHVkNTU4XHViMjk0IFAmIzM5OyYjMzk7XHViNGU0IFx1YzkxMVx1YzVkMFx1YzExYywgfFBbMV0tUCYjMzk7JiMzOTtbMV18K3xQWzJdLVAmIzM5OyYjMzk7WzJdfCsmaGVsbGlwOyt8UFtOXS1QJiMzOTsmIzM5O1tOXXxcdWM3NzQgXHVjZDVjXHVjMThjXHVhYzAwIFx1YjQyMCBcdWI1NGMsIFx1YWRmOCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEmbGU7TiZsZTsxMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWM4MTBcdWM3NTggeCwgeSBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzc0IDBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM4ODVcdWI4Y2NcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQmbmJzcDtcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MDhcdWIzMDBcL1x1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi0zPFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDhcL2ZpZy5QTkdcIiBzdHlsZT1cImhlaWdodDoyMzdweDsgd2lkdGg6NDg1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyMjgwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3F1YXJlIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHNxdWFyZSBhdCBbMCwgMV0gKiBbMCwgMV0gdGhhdCBoYXMgTiBwb2ludHMgKCBQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIC4uLiwgUDxzdWI+TjxcL3N1Yj4gKSBpbiB0aGUgc3F1YXJlICh5b3UgbWF5IGFzc3VtZSB0aGF0IGRpZmZlcmVudCBwb2ludHMgY2FuIGJlIGF0IHRoZSBzYW1lIHBvc2l0aW9uKSwgd2UgY2FuIGNvbm5lY3QgdGhlIE4gcG9pbnRzIGFuZCB0aGUgZm91ciBjb3JuZXJzIG9mIHRoZSBzcXVhcmUgd2l0aCBzb21lIGxpbmUgc2VnbWVudHMgc28gdGhhdCB0aHJvdWdoIHRoZXNlIHNlZ21lbnRzIGFueSB0d28gb2YgdGhlIE4rNCBwb2ludHMgY2FuIHJlYWNoIGVhY2ggb3RoZXIgKGRpcmVjdGx5IG9yIGluZGlyZWN0bHkpLiBUaGUgZ3JhcGggbGVuZ3RoIGlzIGRlZmluZWQgYXMgdGhlIHRvdGFsIGxlbmd0aCBvZiB0aGUgbGluZSBzZWdtZW50cy4gV2hlbiBOIHBvaW50cyYjMzk7IHBvc2l0aW9ucyBhcmUgZml4ZWQsIHRoZXJlIG11c3QgZXhpc3QgYSB3YXkgb2YgY29ubmVjdGluZyB0aGVtLCBzdWNoIHRoYXQgaXQgd2lsbCBtYWtlIHRoZSBzaG9ydGVzdCBncmFwaCBsZW5ndGguIFdlIGNhbiB1c2UgTEVOIChQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIC4uLiwgUDxzdWI+TjxcL3N1Yj4pIHRvIHJlY29yZCB0aGUgZ3JhcGggbGVuZ3RoIHVzaW5nIHRoaXMgd2F5IG9mIGNvbm5lY3RpbmcuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRoaXMgc2l0dWF0aW9uLCBMRU4gKFA8c3ViPjE8XC9zdWI+LCBQPHN1Yj4yPFwvc3ViPiwgLi4uLCBQPHN1Yj5OPFwvc3ViPikgaXMgYSBmdW5jdGlvbiBvZiBQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIC4uLiwgUDxzdWI+TjxcL3N1Yj4uIFdoZW4gUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+IGNoYW5nZSB0aGVpciBwb3NpdGlvbnMsIExFTiAoUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+KSBhbHNvIGNoYW5nZXMuIEl0JiMzOTtzIGVhc3kgdG8gcHJvdmUgdGhhdCB0aGVyZSBleGlzdCBzb21lIFA8c3ViPjE8XC9zdWI+JiMzOTssIFA8c3ViPjI8XC9zdWI+JiMzOTssIC4uLiwgUDxzdWI+TjxcL3N1Yj4mIzM5OyBpbiB0aGUgc3F1YXJlIHN1Y2ggdGhhdCBMRU4gKFA8c3ViPjE8XC9zdWI+JiMzOTssIFA8c3ViPjI8XC9zdWI+JiMzOTssIC4uLiwgUDxzdWI+TjxcL3N1Yj4mIzM5OykgaXMgYXQgaXRzIG1pbmltdW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBpbml0aWFsIHBvc2l0aW9ucyBvZiBOIHBvaW50cywgeW91ciB0YXNrIGlzIHRvIGZpbmQgb3V0IE4gcG9pbnRzIFA8c3ViPjE8XC9zdWI+JnF1b3Q7LCBQPHN1Yj4yPFwvc3ViPiZxdW90OywgLi4uLCBQPHN1Yj5OPFwvc3ViPiZxdW90OyBpbiB0aGUgc3F1YXJlIHN1Y2ggdGhhdCB8UDxzdWI+MTxcL3N1Yj5QPHN1Yj4xPFwvc3ViPiZxdW90O3wgKyB8UDxzdWI+MjxcL3N1Yj5QPHN1Yj4yPFwvc3ViPiZxdW90O3wgKyAuLi4gKyB8UDxzdWI+TjxcL3N1Yj5QPHN1Yj5OPFwvc3ViPiZxdW90O3wgaXMgbWluaW11bSBhbmQgTEVOIChQPHN1Yj4xPFwvc3ViPiZxdW90OywgUDxzdWI+MjxcL3N1Yj4mcXVvdDssIC4uLiwgUDxzdWI+TjxcL3N1Yj4mcXVvdDspID0gTEVOIChQPHN1Yj4xPFwvc3ViPiYjMzk7LCBQPHN1Yj4yPFwvc3ViPiYjMzk7LCAuLi4sIFA8c3ViPk48XC9zdWI+JiMzOTspIC4gWW91IGFyZSByZXF1ZXN0ZWQgdG8gb3V0cHV0IHRoZSB2YWx1ZSBvZiB8UDxzdWI+MTxcL3N1Yj5QPHN1Yj4xPFwvc3ViPiZxdW90O3wgKyB8UDxzdWI+MjxcL3N1Yj5QPHN1Yj4yPFwvc3ViPiZxdW90O3wgKyAuLi4gKyB8UDxzdWI+TjxcL3N1Yj5QPHN1Yj5OPFwvc3ViPiZxdW90O3wsIHdoZXJlIHxQPHN1Yj5pPFwvc3ViPlA8c3ViPmk8XC9zdWI+JnF1b3Q7fCBpcyB0aGUgZGlzdGFuY2UgYmV0d2VlbiBQPHN1Yj5pPFwvc3ViPiBhbmQgUDxzdWI+aTxcL3N1Yj4mcXVvdDsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDhcL2ZpZy5QTkdcIiBzdHlsZT1cImhlaWdodDoyMzdweDsgb3BhY2l0eTowLjk7IHdpZHRoOjQ4NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBGaWd1cmUtMSBnaXZlcyB0aGUgaW5pdGlhbCBwb3NpdGlvbiBvZiBQPHN1Yj4xPFwvc3ViPiBhbmQgdGhlIHdheSBvZiBjb25uZWN0aW5nIHRvIG9idGFpbiBMRU4gKFA8c3ViPjE8XC9zdWI+KS4gSW4gRmlndXJlLTIsIGl0IGdpdmVzIHRoZSBwb3NpdGlvbiBvZiBQPHN1Yj4xPFwvc3ViPiZxdW90Oywgd2hpY2ggaXMgYXQgdGhlIGNlbnRlciBvZiB0aGUgc3F1YXJlLCBhbmQgdGhlIHdheSBvZiBjb25uZWN0aW5nIHRvIG9idGFpbiBMRU4gKFA8c3ViPjE8XC9zdWI+JnF1b3Q7KS4gSXQgY2FuIGJlIHByb3ZlZCB0aGF0IExFTiAoUDxzdWI+MTxcL3N1Yj4mcXVvdDspID0gTEVOIChQPHN1Yj4xPFwvc3ViPiZyc3F1bzspOyB5b3VyIGpvYiBpcyB0byBvdXRwdXQgdGhlIGRpc3RhbmNlIGJldHdlZW4gUDxzdWI+MTxcL3N1Yj4gYW5kIFA8c3ViPjE8XC9zdWI+JnF1b3Q7LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIHNldmVyYWwgdGVzdCBjYXNlcy4gRm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgZmlyc3QgbGluZSBjb25zaXN0cyBvZiBvbmUgaW50ZWdlciBOICgxICZsdDs9IE4gJmx0Oz0gMTAwKSwgdGhlIG51bWJlciBvZiBwb2ludHMsIGFuZCBOIGxpbmVzIGZvbGxvdyB0byBnaXZlIHRoZSBjb29yZGluYXRlcyBmb3IgZXZlcnkgcG9pbnQgaW4gdGhlIGZvbGxvd2luZyBmb3JtYXQ6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPnggeSZuYnNwOzxcL3A+XHJcblxyXG48cD5IZXJlLCB4IGFuZCB5IGFyZSBmbG9hdCBudW1iZXJzIHdpdGhpbiB0aGUgdmFsdWUgWzAsIDFdLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BIHRlc3QgY2FzZSBvZiBOID0gMCBpbmRpY2F0ZXMgdGhlIGVuZCBvZiBpbnB1dCwgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IHRoZSB2YWx1ZSBvZiB8UDxzdWI+MTxcL3N1Yj5QPHN1Yj4xPFwvc3ViPiZxdW90O3wgKyB8UDxzdWI+MjxcL3N1Yj5QPHN1Yj4yPFwvc3ViPiZxdW90O3wgKyAuLi4gKyB8UDxzdWI+TjxcL3N1Yj5QPHN1Yj5OPFwvc3ViPiZxdW90O3wuIFRoZSB2YWx1ZSBzaG91bGQgYmUgcm91bmRlZCB0byB0aHJlZSBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==