프로그램 명: triangulate
제한시간: 1
초
좌표 평면 상에 n 개의 점으로 이루어진 볼록한 다각형이 주어진다. 이 다각형은
아래 그림 처럼 n - 2개의 삼각형으로 나뉘어질수 있다.
다각형을 삼각형으로 나누는 방법은 여러가지가 있을 수 있다. 이 중에서 우리는
나누어진 삼각형들의 둘레의 합이 가장 작게끔 만들고 싶다. 이 때의 삼각형들의
둘레의 합을 출력하는 프로그램을 작성하시오.
입력 형식
첫 번째 줄의 정수는 다각형의 점의 개수 n(3 <= n <= 50)을 나타낸다. 둘째
줄 부터 n 개의 줄에 걸쳐 각 점의 좌표가 시계 방향 순서대로 들어온다. 좌표는 x
좌표와 y 좌표가 공백을 하나 사이에 두고 주어진다. 좌표의 범위는 -1000 이상
1000 이하의 정수 값이다.
출력 형식
n 각형을 삼각형으로 나누었을 때 만들수 있는 최소의 삼각형 둘레의 합을 소수점
셋째자리에서 반올림하여 출력한다.
입출력 예
입력
7
5 11
10 8
11 5
9 0
3 0
0 3
1 7
출력
69.43
출처:
채점 데이터:
// 테스트 데이터가 부실함..
[질/답]
[제출 현황]
[푼 후(0)]