시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 53 | 13 | 11 | 28.205% |
질량이 mi, 길이가 2, 높이가 h인 직사각형이 N개가 있다. 이 직사각형은 2차원 평면에 다음과 같이 쌓여져 있다.
직사각형의 x중심은 아랫변의 중점이다.
하나 또는 그 이상 직사각형의 무게중심은 직사각형의 x좌표와 무게를 이용해서 아래와 같이 계산할 수 있다.
\[\text{직사각형의 무게중심} = \frac{\sum_{i}{m_i \cdot (\text{직사각형 }i\text{의 }x\text{중심})}}{\sum_{i}{m_i}}\]
각 직사각형 A보다 위에 있는 직사각형의 무게중심과 A의 x중심의 거리가 많아야 1이 되도록 직사각형을 쌓는다면, 안정한 쌓기라고 한다.
직사각형을 안정하게 쌓는다면, 직사각형은 무너지지 않을 것이다. 왼쪽 그림은 안정한 배치가 아니다. 그 이유는 가장 위의 두 직사각형의 무게중심과 바로 아래있는 직사각형의 x중심의 거리가 1을 넘기 때문이다. 오른족 그림은 안정한 쌓기이다.
모든 직사각형의 질량이 주어졌을 때, 모든 직사각형의 꼭짓점 중 가장 오른쪽에 있는 꼭짓점이 크게 쌓는 방법을 구하는 프로그램을 작성하시오. 이때, 직사각형은 안정한 쌓기이어야 하고, 입력으로 주어진 순서대로 쌓아야 한다.
첫째 줄에 직사각형의 개수 N이 주어진다. (2 ≤ N ≤ 300,000)
다음 N개 줄에는 직사각형의 질량이 아래 직사각형부터 위 직사각형까지 순서대로 주어진다. 질량은 10,000보다 작거나 같은 양의 정수이다.
첫째 줄에 안정하게 쌓는 방법 중에서 가장 오른쪽 꼭짓점이 클 때의 오른쪽 꼭짓점의 x좌표를 출력한다. 정답과의 오차는 0.000001까지 허용한다.
2 1 1
1.000000
3 1 1 1
1.500000
3 1 1 9
1.900000
Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #5 5번