시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB235463927.273%

문제

저출산 때문에 가장 큰 고통을 받고 있는 산업분야라고 하면 역시 교육을 뽑을 수 있겠다.

점점 줄어들어만 가는 학생들 때문에 너도나도 앞장서서 자신만의 독특한 교육 아이템을 광고하곤 하는데, 이는 2D 나라에 있는 일루 유치원 역시 예외가 아니었다.

일루 유치원에서는 재학생들을 위한 놀이 활동이자 신입생 유치의 일환으로 특대형 이진 모빌 만들기에 도전하고자 한다.

일루 유치원에서 만들고자 하는 이진 모빌은 아래와 같은 모양새를 띄고 있다.

  1. 일루 유치원은 2D나라에 존재한다. 따라서 Z축이 없고, 중력은 -Y축 방향으로 작용하고 있다.
  2. 모빌은 나무 막대와 구슬, 그리고 이들을 연결하는 실로 이루어져 있다.
  3. 모든 막대는 각각 하나의 실에 매달려있으며, 1번 막대를 매달고 있는 실은 천장에 붙어있다.
  4. 각 막대의 양 끝에는 늘 실이 매달려있으며, 해당 실의 반대(아래)쪽에는 나무 막대 혹은 구슬이 매달려 있을 수 있다.
  5. 구슬들은 고유한 무게를 지니며, 막대와 실은 무게가 없다.
  6. 나무 막대와 구슬은 부피가 0인 선으로 봐도 좋으며, 구슬 역시 반지름이 0에 가까운 질량점이라고 생각할 수 있다.
  7. 모든 나무 막대는 모빌이 완성된 시점에서 수평하게(X축에 평행하게) 매달려있어야 한다.

한 편, 일루 원장선생님은 모빌을 전시하기 위한 공간 확보에 어려움을 겪고 있었다. 재료들은 있지만 완성된 모빌의 크기가 얼마나 될지 알 수가 없었기 때문이다.
일루 원장님의 절친한 친구인 당신은 그의 유치원 경영을 도와주고자 한다. 나무 막대들과 구슬간의 연결 상태가 주어질 때, 주어진 모빌의 가로 너비를 출력하는 프로그램을 작성하라.

입력

첫 줄에는 테스트 케이스의 수 \(T\)가 주어진다.

각 테스트 케이스의 첫 줄에는 나무 막대의 수 \(n(1 \leq n \leq 100,000)\)이 주어진다. 다음 \(n\) 개의 줄에 각 나무 막대의 길이를 나타내는 정수 \(len\) (\(1 \leq len \leq 1,000\))과 왼쪽 / 오른쪽 실의 반대편에 매달린 물체의 정보를 나타내는 두 정수 \(l, r\)이 공백으로 구분되어 주어진다. \(-n \leq l \leq -1\) 일 경우에는 \(-l\) 번 나무막대가 왼쪽 끝에 달려 있다는 뜻이며, \(1 \leq l \leq 100,000\)일 경우에는 왼쪽 끝에 해당 중량의 구슬이 달려있다는 뜻이다. \(r\) 역시 오른쪽 끝에 달려있는 정보를 표기한다는 점을 제외하면 \(l\)과 같이 이해하면 된다.

입력으로는 나무 막대와 구슬간의 연결상태, 각 나무 막대의 길이, 각 구슬의 중량이 주어진다.

모든 막대는 한 연결된 컴포넌트의 구성원임이 보장된다.

출력

각 테스트 케이스당 한 줄에 걸쳐 모빌의 폭을 출력한다.

\(10^{-6}\) 이하의 절대 / 상대오차는 정답으로 인정한다.

예제 입력 1

1
3
10 -2 -3
2 100 50
8 75 75

예제 출력 1

14.66666666666

힌트

예제를 그림으로 그리면 다음과 같다.

출처

Contest > Coder's High > Coder's High 2015 Side Contest B1번

  • 문제를 만든 사람: tae