33478번 - 재우의 수영 대회 서브태스크스페셜 저지

문제

2023년 2학기, MatKor Cup에 단골로 등장할 사건이 재우에게 벌어졌다. 바로 1년 전 F를 받은 수영 과목을 재수강하게 된 것이었다. 원래 재우와 수영은 재우가 F를 받으며 등장한 문제, 그다음 학기에 수강했다면 드랍이 가능했을 것이라는 문제의 두 문제로 끝이 날 예정이었지만, 이 재수강으로 인해 재수강을 하는 문제, 그리고 실제로는 하지 않았지만 삼수강을 한 문제, 마찬가지로 실제는 아니지만 수영 대회를 개최하는 문제까지 만들어지게 되었다. 이로써 재우와 수영은 2회부터 이번 6회 대회까지 5개의 대회에 6번 문제로 등장하게 되었다.

수영 과목 삼수강을 마친 재우는 이제 수영을 마스터해, 수영 대회에 출전하게 되었다. 지난 2024 KAIST 14th ICPC Mock Competition에 참여한 재우는 아래 포스터를 보고 고려대학교에도 수영 대회가 있으면 좋겠다는 생각에 고려대학교 수영 대회를 개최하기로 했다.

수영 대회의 수영장 레인은 원형으로 되어 있고, 수영장의 출입구는 원주 위의 서로 다른 세 점 $A,ドル $B,ドル $C$에 위치하고 있다. 그리고 세 출입구 사이에는 안전 요원들이 다닐 수 있는 세 개의 주 안전 통로가 세 출입구를 각각 꼭짓점으로 하는 삼각형의 형태로 존재한다. 또한 본부는 삼각형의 내부에 위치하여 세 개의 안전 통로로부터 거리가 같은 점, 즉 내심 $I$에 위치하고 있다. 이제 재우는 안전을 위한 추가적인 직선형 통로인 부 안전 통로를 포함해 수영장을 아래와 같이 설계했다.

• 먼저 세 출입구 $A,ドル $B,ドル $C$ 중 주 출입구, 부 출입구, 비상 출입구를 각각 서로 다르게 하나씩 출입구의 종류를 배정한다.
  • 주 출입구가 아닌 두 출입구를 기준으로 나뉘는 두 원호 모양의 레인 중 주 출입구를 포함하지 않는 부분을 위험 레인이라 하자.
• 주 출입구에서 본부 $I$ 방향으로 반직선 모양의 부 안전 통로를 반대쪽 레인을 만날 때까지 건설한다. 이때 반대쪽 레인의 점을 $D$라고 하고, 이 점을 체크포인트라고 하자. 이 점은 위험 레인 위에 있음은 증명할 수 있다.
• 위험 레인 위의 서로 다른 두 점 $E$와 $F$를 다음 조건을 만족하게 고르고, 이 두 점을 관리 경계점이라고 하자.
  • 부 출입구부터 비상 출입구까지 위험 레인으로 수영할 때, 부 출입구, $E,ドル $D,ドル $F,ドル 비상 출입구의 순서로 지나가며, 이 점들은 모두 다르다.
  • 부 출입구부터 비상 출입구까지 위험 레인으로 수영할 때, $E$부터 $D$까지의 거리와 $D$부터 $F$까지의 거리가 같아지도록 한다. 여기서 거리는 직선이 아닌 원호 위에서 실제로 수영하는 거리이다.
• 부 출입구와 가까운 관리 경계점인 $E$에서 본부 $I$ 방향으로 반직선 모양의 부 안전 통로를 반대쪽 레인을 만날 때까지 건설한다. 이때 반대쪽 레인의 점을 $S$라고 하고, 이 점을 수영 대회에서 출발 지점이라고 하자.
• 비상 출입구와 가까운 관리 경계점인 $F$와 주 출입구를 끝점으로 하는 선분의 부 안전 통로를 건설한다. 이 통로는 부 출입구와 비상 출입구를 잇는 주 안전 통로와 한 점 $G$에서 만남을 증명할 수 있는데, 이 점을 제1교차점이라 한다.
• 출발 지점 $S$와 체크 포인트 $D$를 끝점으로 하는 선분의 부 안전 통로를 건설한다.
• 제1교차점 $G$와 본부 $I$를 끝점으로 하는 선분의 부 안전 통로를 건설한다. 이 통로는 $S$와 $D$를 잇는 부 안전 통로와 한점 $H$에서 만남을 증명할 수 있는데, 이 점을 제2교차점이라 한다.

재우는 제2교차점 $H$에서 본부 $I$와 제1교차점 $G$를 가는 거리 중 큰 값을 최대한 작게 만들고 싶다. 즉, 재우는 출입구 세 개의 종류 배정, $E$와 $F$의 위치를 설계할 수 있는 가능한 모든 경우에 대해 $\max\left( \overline{GH} ,\overline{HI} \right)$의 하한을 알고 싶다. 구체적으로, 가능한 모든 경우에 대해 $m\le\max\left( \overline{GH} ,\overline{HI} \right)$을 만족하는 $m$의 최댓값을 찾고 싶다. 여기서 거리는 직선거리를 의미한다.

재우가 주 안전 통로 세 개의 길이 $a=\overline{BC},ドル $b=\overline{CA},ドル $c=\overline{AB}$를 알고 있을 때, 재우가 출입구 세 개의 종류 배정, $E$와 $F$의 위치로 설계할 수 있는 모든 경우에 대해 $\max\left( \overline{GH} ,\overline{HI} \right)$ 값의 하한을 구해 보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 10^5)$가 주어진다.

두 번째 줄부터 $T$개의 줄에 걸쳐 각각의 테스트 케이스의 주 안전 통로 세 개의 길이 $a,b,c(1\le a\le b\le c\le 10^{9}$; $a+b>c)$가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스 별로 한 줄에 한 개씩 재우가 출입구 세 개의 종류 배정, $E$와 $F$의 위치로 설계할 수 있는 모든 경우 중 $\max\left( \overline{GH} ,\overline{HI} \right)$의 하한을 출력한다.

정답과의 절대/상대 오차는 10ドル^{-9}$까지 허용한다.

제한

서브태스크

힌트