시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 705 375 306 55.335%

문제

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

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

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

입력

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

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

출력

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

예제 입력 1

3
1.0 1.0
2.0 2.0
2.0 4.0

예제 출력 1

3.41
W3sicHJvYmxlbV9pZCI6IjQzODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjYzRcdWM3OTBcdWI5YWMgXHViOWNjXHViNGU0XHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIzYzRcdWQ2MDRcdWM3NzRcdWIyOTQgXHVjNmIwXHVjOGZjXHVjNzU4IFx1YzJlMFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHVjODFjIFx1YjNjNFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWM1NDRcdWJiMzRcdWI4MDdcdWFjOGNcdWIwOTggXHViMTEwXHViZTBjXHViN2VjXHVjODM4IFx1Yzc4OFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YmNjNFx1YjRlNFx1Yzc0NCBcdWM3NzRcdWM1YjRcdWMxMWMgXHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1ZDU1OFx1YjA5OCBcdWI5Y2NcdWI0ZTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWJjYzRcdWM3OTBcdWI5YWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQwIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWMxMjBcdWM3NDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViY2M0XHVjNzQ0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM3NDAgXHVkNjE1XHVkMGRjXHVjNzc0XHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJhYThcdWI0ZTAgXHViY2M0XHViNGU0XHVjNzQwIFx1YmNjNFx1Yzc5MFx1YjlhYyBcdWM3MDRcdWM3NTggXHVjMTIwXHVjNzQ0IFx1ZDFiNVx1ZDU3NCBcdWMxMWNcdWI4NWMgXHVjOWMxXC9cdWFjMDRcdWM4MTFcdWM4MDFcdWM3M2NcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHViY2M0XHViNGU0XHVjNzc0IDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWIxOTNcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWMxMjBcdWM3NDQgXHVkNTU4XHViMDk4IFx1Yzc3NFx1Yzc0NCBcdWI1NGNcdWI5YzhcdWIyZTQgXHViNDUwIFx1YmNjNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViOWNjXHVkMDdjXHVjNzU4IFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YywgXHViY2M0XHVjNzkwXHViOWFjXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2M0XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBuICZsZTsgMTAwKTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjgmbmJzcDtcdWM5MDRcdWJkODBcdWQxMzAgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWJjYzRcdWM3NTggeCwgeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMyZTRcdWMyMTggXHVkNjE1XHVkMGRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjZDVjXHViMzAwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWI0NThcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgMTAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzU5MVx1Yzc1OCBcdWMyZTRcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MDhcdWIzMDBcL1x1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi0yPFwvc3VwPlx1YWU0Y1x1YzljMCBcdWQ1YzhcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDM4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkZyZWNrbGVzIiwiZGVzY3JpcHRpb24iOiI8cD5JbiBhbiBlcGlzb2RlIG9mIHRoZSBEaWNrIFZhbiBEeWtlIHNob3csIGxpdHRsZSBSaWNoaWUgY29ubmVjdHMgdGhlIGZyZWNrbGVzIG9uIGhpcyBEYWQmIzM5O3MgYmFjayB0byBmb3JtIGEgcGljdHVyZSBvZiB0aGUgTGliZXJ0eSBCZWxsLiBBbGFzLCBvbmUgb2YgdGhlIGZyZWNrbGVzIHR1cm5zIG91dCB0byBiZSBhIHNjYXIsIHNvIGhpcyBSaXBsZXkmIzM5O3MgZW5nYWdlbWVudCBmYWxscyB0aHJvdWdoLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciBEaWNrJiMzOTtzIGJhY2sgdG8gYmUgYSBwbGFuZSB3aXRoIGZyZWNrbGVzIGF0IHZhcmlvdXMgKHgseSkgbG9jYXRpb25zLiBZb3VyIGpvYiBpcyB0byB0ZWxsIFJpY2hpZSBob3cgdG8gY29ubmVjdCB0aGUgZG90cyBzbyBhcyB0byBtaW5pbWl6ZSB0aGUgYW1vdW50IG9mIGluayB1c2VkLiBSaWNoaWUgY29ubmVjdHMgdGhlIGRvdHMgYnkgZHJhd2luZyBzdHJhaWdodCBsaW5lcyBiZXR3ZWVuIHBhaXJzLCBwb3NzaWJseSBsaWZ0aW5nIHRoZSBwZW4gYmV0d2VlbiBsaW5lcy4gV2hlbiBSaWNoaWUgaXMgZG9uZSB0aGVyZSBtdXN0IGJlIGEgc2VxdWVuY2Ugb2YgY29ubmVjdGVkIGxpbmVzIGZyb20gYW55IGZyZWNrbGUgdG8gYW55IG90aGVyIGZyZWNrbGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyAwICZsdDsgbiAmbHQ7PSAxMDAsIHRoZSBudW1iZXIgb2YgZnJlY2tsZXMgb24gRGljayYjMzk7cyBiYWNrLiBGb3IgZWFjaCBmcmVja2xlLCBhIGxpbmUgZm9sbG93czsgZWFjaCBmb2xsb3dpbmcgbGluZSBjb250YWlucyB0d28gcmVhbCBudW1iZXJzIGluZGljYXRpbmcgdGhlICh4LHkpIGNvb3JkaW5hdGVzIG9mIHRoZSBmcmVja2xlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBwcmludHMgYSBzaW5nbGUgcmVhbCBudW1iZXIgdG8gdHdvIGRlY2ltYWwgcGxhY2VzOiB0aGUgbWluaW11bSB0b3RhbCBsZW5ndGggb2YgaW5rIGxpbmVzIHRoYXQgY2FuIGNvbm5lY3QgYWxsIHRoZSBmcmVja2xlcy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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