시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 263 149 116 64.088%

문제

도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널부러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다.

  • 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다.
  • 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다.

별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오.

입력

첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100)

둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째자리까지 주어진다.

출력

첫째 줄에 정답을 출력한다. 절대/상대 오차는 10-2까지 허용한다.

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41
W3sicHJvYmxlbV9pZCI6IjQzODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYzRcdWM3OTBcdWI5YWMgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzYzRcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNmIwXHVjOGZjXHVjNzU4IFx1YzJlMFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YjNjNFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHViMTEwXHViZDgwXHViN2VjXHVjODM4IFx1Yzc4OFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YmNjNFx1YjRlNFx1Yzc0NCBcdWM3NzRcdWM1YjRcdWMxMWMgXHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJjYzRcdWM3OTBcdWI5YWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMxMjBcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViY2M0XHVjNzQ0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDAgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHViY2M0XHViNGU0XHVjNzQwIFx1YmNjNFx1Yzc5MFx1YjlhYyBcdWM3MDRcdWM3NTggXHVjMTIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWMxMWNcdWI4NWMgXHVjOWMxXC9cdWFjMDRcdWM4MTFcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViY2M0XHViNGU0XHVjNzc0IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWMxMjBcdWM3NDQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1Yzc0NCBcdWI1NGNcdWI5YzhcdWIyZTQgXHViNDUwIFx1YmNjNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOWNjXHVkMDdjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YywgXHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2M0XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjgmbmJzcDtcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWJjYzRcdWM3NTggeCwgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyZTRcdWMyMTggXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjZDVjXHViMzAwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHViMjk0IDEwPHN1cD4tMjxcL3N1cD5cdWFlNGNcdWM5YzAgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzODYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGcmVja2xlcyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gYW4gZXBpc29kZSBvZiB0aGUgRGljayBWYW4gRHlrZSBzaG93LCBsaXR0bGUgUmljaGllIGNvbm5lY3RzIHRoZSBmcmVja2xlcyBvbiBoaXMgRGFkJiMzOTtzIGJhY2sgdG8gZm9ybSBhIHBpY3R1cmUgb2YgdGhlIExpYmVydHkgQmVsbC4gQWxhcywgb25lIG9mIHRoZSBmcmVja2xlcyB0dXJucyBvdXQgdG8gYmUgYSBzY2FyLCBzbyBoaXMgUmlwbGV5JiMzOTtzIGVuZ2FnZW1lbnQgZmFsbHMgdGhyb3VnaC48XC9wPlxyXG5cclxuPHA+Q29uc2lkZXIgRGljayYjMzk7cyBiYWNrIHRvIGJlIGEgcGxhbmUgd2l0aCBmcmVja2xlcyBhdCB2YXJpb3VzICh4LHkpIGxvY2F0aW9ucy4gWW91ciBqb2IgaXMgdG8gdGVsbCBSaWNoaWUgaG93IHRvIGNvbm5lY3QgdGhlIGRvdHMgc28gYXMgdG8gbWluaW1pemUgdGhlIGFtb3VudCBvZiBpbmsgdXNlZC4gUmljaGllIGNvbm5lY3RzIHRoZSBkb3RzIGJ5IGRyYXdpbmcgc3RyYWlnaHQgbGluZXMgYmV0d2VlbiBwYWlycywgcG9zc2libHkgbGlmdGluZyB0aGUgcGVuIGJldHdlZW4gbGluZXMuIFdoZW4gUmljaGllIGlzIGRvbmUgdGhlcmUgbXVzdCBiZSBhIHNlcXVlbmNlIG9mIGNvbm5lY3RlZCBsaW5lcyBmcm9tIGFueSBmcmVja2xlIHRvIGFueSBvdGhlciBmcmVja2xlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgMCAmbHQ7IG4gJmx0Oz0gMTAwLCB0aGUgbnVtYmVyIG9mIGZyZWNrbGVzIG9uIERpY2smIzM5O3MgYmFjay4gRm9yIGVhY2ggZnJlY2tsZSwgYSBsaW5lIGZvbGxvd3M7IGVhY2ggZm9sbG93aW5nIGxpbmUgY29udGFpbnMgdHdvIHJlYWwgbnVtYmVycyBpbmRpY2F0aW5nIHRoZSAoeCx5KSBjb29yZGluYXRlcyBvZiB0aGUgZnJlY2tsZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Zb3VyIHByb2dyYW0gcHJpbnRzIGEgc2luZ2xlIHJlYWwgbnVtYmVyIHRvIHR3byBkZWNpbWFsIHBsYWNlczogdGhlIG1pbmltdW0gdG90YWwgbGVuZ3RoIG9mIGluayBsaW5lcyB0aGF0IGNhbiBjb25uZWN0IGFsbCB0aGUgZnJlY2tsZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Contest > Waterloo's local Programming Contests > 23 September, 2000 A번

  • 잘못된 조건을 찾은 사람: cubelover
  • 문제를 번역한 사람: kks227
  • 문제의 오타를 찾은 사람: solarmagic