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

문제

[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 좌표가 주어진다. 입력의 마지막 줄에는 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+XHJcblxyXG48cD5cdWM5ODksIExlbihQJnF1b3Q7KT1MZW4oUCYjMzk7KVx1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgUCZxdW90O1x1YjRlNCBcdWM5MTFcdWM1ZDBcdWMxMWMsIHxQWzFdLVAmcXVvdDtbMV18ICsgfFBbMl0tUCZxdW90O1syXXwgKyAmaGVsbGlwOyArIHxQW05dLVAmcXVvdDtbTl18XHVjNzc0IFx1Y2Q1Y1x1YzE4Y1x1YWMwMCBcdWI0MjAgXHViNTRjLCBcdWFkZjggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxICZsZTsgTiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YzgxMFx1Yzc1OCB4LCB5IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVkNTU4XHViMDk4IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjODhjXHVkNDVjXHViMjk0IFx1YzE4Y1x1YzIyYlx1YzgxMCBcdWM1ZWNcdWIzNWYgXHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljOCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0Jm5ic3A7XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tMzxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC9maWcuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MjM3cHg7IHdpZHRoOjQ4NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMjI4MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNxdWFyZSIsImRlc2NyaXB0aW9uIjoiPHA+R2l2ZW4gYSBzcXVhcmUgYXQgWzAsIDFdICogWzAsIDFdIHRoYXQgaGFzIE4gcG9pbnRzICggUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+ICkgaW4gdGhlIHNxdWFyZSAoeW91IG1heSBhc3N1bWUgdGhhdCBkaWZmZXJlbnQgcG9pbnRzIGNhbiBiZSBhdCB0aGUgc2FtZSBwb3NpdGlvbiksIHdlIGNhbiBjb25uZWN0IHRoZSBOIHBvaW50cyBhbmQgdGhlIGZvdXIgY29ybmVycyBvZiB0aGUgc3F1YXJlIHdpdGggc29tZSBsaW5lIHNlZ21lbnRzIHNvIHRoYXQgdGhyb3VnaCB0aGVzZSBzZWdtZW50cyBhbnkgdHdvIG9mIHRoZSBOKzQgcG9pbnRzIGNhbiByZWFjaCBlYWNoIG90aGVyIChkaXJlY3RseSBvciBpbmRpcmVjdGx5KS4gVGhlIGdyYXBoIGxlbmd0aCBpcyBkZWZpbmVkIGFzIHRoZSB0b3RhbCBsZW5ndGggb2YgdGhlIGxpbmUgc2VnbWVudHMuIFdoZW4gTiBwb2ludHMmIzM5OyBwb3NpdGlvbnMgYXJlIGZpeGVkLCB0aGVyZSBtdXN0IGV4aXN0IGEgd2F5IG9mIGNvbm5lY3RpbmcgdGhlbSwgc3VjaCB0aGF0IGl0IHdpbGwgbWFrZSB0aGUgc2hvcnRlc3QgZ3JhcGggbGVuZ3RoLiBXZSBjYW4gdXNlIExFTiAoUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+KSB0byByZWNvcmQgdGhlIGdyYXBoIGxlbmd0aCB1c2luZyB0aGlzIHdheSBvZiBjb25uZWN0aW5nLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0aGlzIHNpdHVhdGlvbiwgTEVOIChQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIC4uLiwgUDxzdWI+TjxcL3N1Yj4pIGlzIGEgZnVuY3Rpb24gb2YgUDxzdWI+MTxcL3N1Yj4sIFA8c3ViPjI8XC9zdWI+LCAuLi4sIFA8c3ViPk48XC9zdWI+LiBXaGVuIFA8c3ViPjE8XC9zdWI+LCBQPHN1Yj4yPFwvc3ViPiwgLi4uLCBQPHN1Yj5OPFwvc3ViPiBjaGFuZ2UgdGhlaXIgcG9zaXRpb25zLCBMRU4gKFA8c3ViPjE8XC9zdWI+LCBQPHN1Yj4yPFwvc3ViPiwgLi4uLCBQPHN1Yj5OPFwvc3ViPikgYWxzbyBjaGFuZ2VzLiBJdCYjMzk7cyBlYXN5IHRvIHByb3ZlIHRoYXQgdGhlcmUgZXhpc3Qgc29tZSBQPHN1Yj4xPFwvc3ViPiYjMzk7LCBQPHN1Yj4yPFwvc3ViPiYjMzk7LCAuLi4sIFA8c3ViPk48XC9zdWI+JiMzOTsgaW4gdGhlIHNxdWFyZSBzdWNoIHRoYXQgTEVOIChQPHN1Yj4xPFwvc3ViPiYjMzk7LCBQPHN1Yj4yPFwvc3ViPiYjMzk7LCAuLi4sIFA8c3ViPk48XC9zdWI+JiMzOTspIGlzIGF0IGl0cyBtaW5pbXVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgaW5pdGlhbCBwb3NpdGlvbnMgb2YgTiBwb2ludHMsIHlvdXIgdGFzayBpcyB0byBmaW5kIG91dCBOIHBvaW50cyBQPHN1Yj4xPFwvc3ViPiZxdW90OywgUDxzdWI+MjxcL3N1Yj4mcXVvdDssIC4uLiwgUDxzdWI+TjxcL3N1Yj4mcXVvdDsgaW4gdGhlIHNxdWFyZSBzdWNoIHRoYXQgfFA8c3ViPjE8XC9zdWI+UDxzdWI+MTxcL3N1Yj4mcXVvdDt8ICsgfFA8c3ViPjI8XC9zdWI+UDxzdWI+MjxcL3N1Yj4mcXVvdDt8ICsgLi4uICsgfFA8c3ViPk48XC9zdWI+UDxzdWI+TjxcL3N1Yj4mcXVvdDt8IGlzIG1pbmltdW0gYW5kIExFTiAoUDxzdWI+MTxcL3N1Yj4mcXVvdDssIFA8c3ViPjI8XC9zdWI+JnF1b3Q7LCAuLi4sIFA8c3ViPk48XC9zdWI+JnF1b3Q7KSA9IExFTiAoUDxzdWI+MTxcL3N1Yj4mIzM5OywgUDxzdWI+MjxcL3N1Yj4mIzM5OywgLi4uLCBQPHN1Yj5OPFwvc3ViPiYjMzk7KSAuIFlvdSBhcmUgcmVxdWVzdGVkIHRvIG91dHB1dCB0aGUgdmFsdWUgb2YgfFA8c3ViPjE8XC9zdWI+UDxzdWI+MTxcL3N1Yj4mcXVvdDt8ICsgfFA8c3ViPjI8XC9zdWI+UDxzdWI+MjxcL3N1Yj4mcXVvdDt8ICsgLi4uICsgfFA8c3ViPk48XC9zdWI+UDxzdWI+TjxcL3N1Yj4mcXVvdDt8LCB3aGVyZSB8UDxzdWI+aTxcL3N1Yj5QPHN1Yj5pPFwvc3ViPiZxdW90O3wgaXMgdGhlIGRpc3RhbmNlIGJldHdlZW4gUDxzdWI+aTxcL3N1Yj4gYW5kIFA8c3ViPmk8XC9zdWI+JnF1b3Q7LiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA4XC9maWcuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MjM3cHg7IG9wYWNpdHk6MC45OyB3aWR0aDo0ODVweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgRmlndXJlLTEgZ2l2ZXMgdGhlIGluaXRpYWwgcG9zaXRpb24gb2YgUDxzdWI+MTxcL3N1Yj4gYW5kIHRoZSB3YXkgb2YgY29ubmVjdGluZyB0byBvYnRhaW4gTEVOIChQPHN1Yj4xPFwvc3ViPikuIEluIEZpZ3VyZS0yLCBpdCBnaXZlcyB0aGUgcG9zaXRpb24gb2YgUDxzdWI+MTxcL3N1Yj4mcXVvdDssIHdoaWNoIGlzIGF0IHRoZSBjZW50ZXIgb2YgdGhlIHNxdWFyZSwgYW5kIHRoZSB3YXkgb2YgY29ubmVjdGluZyB0byBvYnRhaW4gTEVOIChQPHN1Yj4xPFwvc3ViPiZxdW90OykuIEl0IGNhbiBiZSBwcm92ZWQgdGhhdCBMRU4gKFA8c3ViPjE8XC9zdWI+JnF1b3Q7KSA9IExFTiAoUDxzdWI+MTxcL3N1Yj4mcnNxdW87KTsgeW91ciBqb2IgaXMgdG8gb3V0cHV0IHRoZSBkaXN0YW5jZSBiZXR3ZWVuIFA8c3ViPjE8XC9zdWI+IGFuZCBQPHN1Yj4xPFwvc3ViPiZxdW90Oy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIEZvciBlYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29uc2lzdHMgb2Ygb25lIGludGVnZXIgTiAoMSAmbHQ7PSBOICZsdDs9IDEwMCksIHRoZSBudW1iZXIgb2YgcG9pbnRzLCBhbmQgTiBsaW5lcyBmb2xsb3cgdG8gZ2l2ZSB0aGUgY29vcmRpbmF0ZXMgZm9yIGV2ZXJ5IHBvaW50IGluIHRoZSBmb2xsb3dpbmcgZm9ybWF0OiZuYnNwOzxcL3A+XHJcblxyXG48cD54IHkmbmJzcDs8XC9wPlxyXG5cclxuPHA+SGVyZSwgeCBhbmQgeSBhcmUgZmxvYXQgbnVtYmVycyB3aXRoaW4gdGhlIHZhbHVlIFswLCAxXS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSB0ZXN0IGNhc2Ugb2YgTiA9IDAgaW5kaWNhdGVzIHRoZSBlbmQgb2YgaW5wdXQsIGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCB0aGUgdmFsdWUgb2YgfFA8c3ViPjE8XC9zdWI+UDxzdWI+MTxcL3N1Yj4mcXVvdDt8ICsgfFA8c3ViPjI8XC9zdWI+UDxzdWI+MjxcL3N1Yj4mcXVvdDt8ICsgLi4uICsgfFA8c3ViPk48XC9zdWI+UDxzdWI+TjxcL3N1Yj4mcXVvdDt8LiBUaGUgdmFsdWUgc2hvdWxkIGJlIHJvdW5kZWQgdG8gdGhyZWUgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d