문제 80
매우 잘 알려진 사실
일감호에 세종대학교 캠퍼스가 들어가지 않는다는 것은 매우 잘 알려진 사실이다.
종이는 일감호와 비슷하게 생긴 직사각형과 세종대학교 캠퍼스와 비슷하게 생긴 삼각형을 가지고 있다.
종이는 세 변의 길이가 $a$, $b$, $c$인 삼각형을 적절히 회전하여 가로 길이가 $W$이고, 세로 길이가 $H$인 직사각형 안에 포함시킬 수 있는지 궁금해한다. 이때 삼각형의 경계가 직사각형의 경계에 닿아도 된다.
입력
첫 번째 줄에 테스트케이스의 개수를 의미하는 정수 $T$가 주어진다. $(1 \le T \le 500)$
두 번째 줄부터 $T$개의 줄에 걸쳐 다섯 정수 $W$, $H$, $a$, $b$, $c$가 공백으로 구분되어 주어진다. $(1 \le W, H, a, b, c \le 10\,000)$
넓이가 양수인 삼각형만 주어진다.
출력
각 테스트케이스마다 삼각형을 적절히 회전하여 직사각형 안에 포함시킬 수 있다면 Yes를, 그렇지 않다면 No를 한 줄에 하나씩 출력한다.
예제 입력 1
3 1 1 1 1 1 1 2 2 1 2 1 3 2 2 3
예제 출력 1
Yes Yes No
공식 해설
꼭짓점 하나를 직사각형 모서리에 놓기
배치한 삼각형의 $x$좌표 최솟값·최댓값과 $y$좌표 최솟값·최댓값을 이루는 꼭짓점을 고르자. 네 극값을 세 꼭짓점이 담당하므로 적어도 한 꼭짓점이 두 방향의 극값을 함께 이룬다. 즉 삼각형을 감싸는 최소 축 정렬 직사각형의 모서리에 꼭짓점 하나가 있다.
따라서 가능한 배치가 있다면 평행이동과 직사각형의 대칭을 이용해 그 꼭짓점을 원점에 두고 나머지 두 꼭짓점을 $[0,W]\times[0,H]$ 안에 놓을 수 있다. 원점에 붙은 변의 길이를 $b,c$, 맞은편 변을 $a$라 하자.
가능한 최대 각과 필요한 각 비교하기
길이가 정해진 선분을 원점에서 직사각형 안에 놓을 수 있는 방향들은 연속한 구간이다. 선분이 들어갈 수 있다면 직사각형의 대각선 방향도 가능하므로 두 변의 방향 구간은 서로 겹친다. 따라서 두 변 사이의 각은 $0$부터 가능한 최대 각까지 연속적으로 만들 수 있다.
최대 각은 한 변을 가장 가로에 가깝게, 다른 변을 가장 세로에 가깝게 놓아 얻는다. $c$를 가로 쪽, $b$를 세로 쪽에 놓을 때 두 끝점의 좌표 제곱은
\[
X_1=\min(c^2,W^2),\qquad Y_1=\max(0,c^2-W^2),
\]
\[
X_2=\max(0,b^2-H^2),\qquad Y_2=\min(b^2,H^2)
\]
이다. $Y_1>H^2$ 또는 $X_2>W^2$이면 해당 변 자체가 들어가지 않으므로 실패이다.
두 극단 방향의 내적은 $\sqrt{X_1X_2}+\sqrt{Y_1Y_2}$이다. 코사인 법칙으로 필요한 각의 내적은 $(b^2+c^2-a^2)/2$이다. 각이 커질수록 내적이 작아지므로, 이 배정에서는
\[
b^2+c^2-a^2\ge2\sqrt{X_1X_2}+2\sqrt{Y_1Y_2}
\]
이면 필요한 각을 만들 수 있다.
경계까지 정수로 판정하기
$P=X_1X_2$, $Q=Y_1Y_2$, $R=b^2+c^2-a^2$라 하자. 위 부등식은 부호를 확인하며 두 번 제곱하여
\[
R\ge0,\qquad Z=R^2-4(P+Q)\ge0,\qquad Z^2\ge64PQ
\]
로 판정할 수 있다. 첫 제곱 후에는 $Z\ge8\sqrt{PQ}$이므로 $Z$의 부호도 확인해야 원래 부등식과 동치이다.
원점에 놓을 꼭짓점 세 가지와 두 변의 가로·세로 배정 두 가지, 총 여섯 경우를 검사한다. 하나라도 성립하면 Yes, 모두 실패하면 No이다. 등호를 허용하므로 경계에 닿는 배치도 포함한다.
마지막 조건의 $Z^2$와 $64PQ$는 입력값보다 훨씬 커진다. 원래 길이뿐 아니라 이 중간값까지 정확히 표현할 수 있는 정수 연산이 필요하다. 테스트케이스마다 상수 개의 경우만 검사하므로 시간복잡도와 추가 공간복잡도는 $O(1)$이다.
구현 · 언어별 풀이
C++ 구현
제곱과 곱을 계산할 때부터 __int128을 사용한다. 마지막 비교만 넓혀서는 앞의 중간 곱이 넘치는 것을 막을 수 없다. 먼저 $R\ge0$과 $Z\ge0$을 확인한 뒤 마지막 제곱 부등식을 판정한다. 비교만 수행하므로 128비트 정수를 출력하는 함수는 필요 없다.
C 구현
GNU __int128로 R,Z와 마지막 제곱·곱을 계산한다. 길이는 10000 이하이지만 Z제곱과 64PQ는 64비트를 넘는다. R과 Z의 부호를 먼저 확인한 뒤 제곱 조건을 검사하고 여섯 배정을 모두 시도한다.
Python 구현
Python int로 R,Z,Z*Z,64*P*Q를 그대로 계산한다. math.sqrt나 epsilon 없이 경계 포함 여부를 정확히 결정한다. 제곱 전에 R>=0, Z>=0을 반드시 확인한다.
Java 구현
길이 제곱은 long에 들어가지만 최종 비교에는 BigInteger가 필요하다. R,Z를 정확히 계산하고 signum() 확인 뒤 Z.multiply(Z)와 64PQ를 비교한다. double로 근사해 경계를 판정하지 않는다.
Rust 구현
모든 식을 i128로 계산한다. 길이 상한 10000에서 최종 항은 대략 $10^{34}$ 이하라 i128 범위 안이다. i64로 곱을 만든 뒤 변환하지 말고 길이부터 승격하며 R,Z 부호를 먼저 확인한다.
JavaScript 구현
길이만 보면 작지만 마지막 조건의 네 번 제곱과 곱은 안전 정수 범위를 훨씬 넘는다. $W,H,a,b,c$를 BigInt로 읽고 좌표 제곱부터 마지막 부등식까지 같은 타입으로 계산한다.
가로·세로 배정 하나에서 구한 $P,Q,R$에 대해 다음처럼 부호를 먼저 확인한 뒤 제곱 비교를 한다.
const z = r * r - 4n * (p + q);
const fits = r >= 0n && z >= 0n && z * z >= 64n * p * q;음수인 $R$이나 $Z$를 제곱만 해서 판정하면 원래 부등식과 달라진다. Math.min·Math.max는 BigInt를 받지 않으므로 조건 연산자로 $X_1,Y_1,X_2,Y_2$를 정하고, 한 변 자체가 직사각형 대각선보다 긴 경우도 공통 풀이대로 제외한다.
꼭짓점 세 가지와 두 변 배정 두 가지를 검사하는 작은 반복문으로 충분하다. 부동소수 각도·삼각함수·epsilon이나 배치 객체를 추가하지 않는다. 등호는 가능으로 처리한다.