Hello BOJ 2022에 B번 문제로 출제되었던 문제입니다. 풀이를 찾지 못해서 질문 올려봅니다.

현재 적당한 boundary value (1000000000 1000000000 2), 40이하 완전 탐색 코드 비교, a + b = c를 만족하는 두 a, b random 값등의 테스트를 해봤는데 문제를 찾지 못했습니다. 출력 문제인줄 알고 다양하게 바꿔보고 해당 알고리즘에 대해서도 고민을 해봤는데 틀린점을 찾지 못하겠습니다.

혹시 위치가 잘못 출력되서 그런가 해서 위치가 맞는지 확인하고 출력하는 코드도 넣어봤는데 똑같은 곳에서 틀리는 것을 보면 그건 아닌 것 같습니다.

구체적인 풀이는 아래와 같습니다.

먼저 첫번째 점을 1, 1을 고정하고 a, b 만큼 떨어진 점들의 집합은 직선의 방정식이 나옵니다.

두번째 점은 x축에 만나는 점으로 설정합니다.

세번째 점은 해당 점의 x값과 같고 직선의 방정식을 만나는 점으로 먼저 설정을 합니다. 이때 두 점 사이의 길이가 c 이면 통과하고 아니라면 왼쪽 아래로 내려가면서 길이를 c와 같게 증가시킵니다. (빨간색 영역은 두번째 점과 떨어진 길이가 똑같은 영역입니다.)

그림판 그림으로 설명하면 아래와 같습니다.

이때 y축에 평행하게 떨어뜨릴때 사각형 밖으로 갔다면 y 값을 8*10^8로 이동시키고 x 값은 직선에 방정식에 따라 이동합니다 (사각형과 만나는 부분과 만나거나 답이 존재하지 않음)

이때 a, b, c에 대한 모든 순열로 시행하면 각이 90도 이상인 삼각형에서 예각인 부분도 커버 가능합니다.

이렇게 했는데 틀리다고 나오더라고요... 혹시 풀이가 있으시거나 틀린 부분, 반례를 알려주실 수 있으시다면 감사하겠습니다.