원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
직각이등변삼각형
원제: 직각이등변삼각형
문제
2차원 평면 위에 서로 다른 개의 점이 있다. 인 각 에 대해, 번째 점의 좌표는 이다.
이등변삼각형이란, 세 변 중 길이가 같은 두 변이 있는 삼각형을 의미한다. 직각삼각형이란, 한 내각이 직각()인 삼각형을 의미한다. 직각삼각형의 빗변이란, 직각삼각형에서 직각과 마주보는 변을 의미하며, 길이가 가장 긴 변이기도 하다.
직각이등변삼각형이란, 직각삼각형이면서 이등변삼각형인 삼각형을 의미한다. 즉, 삼각형의 한 내각이 직각이고, 빗변이 아닌 두 변의 길이가 서로 같은 삼각형을 의미한다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
다음 두 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 구하는 프로그램을 작성하라.
- 개의 점 모두 직각이등변삼각형의 경계(변 위)나 내부에 위치한다. 어떤 점이 직각이등변삼각형의 꼭짓점에 위치하는 경우도 경계에 위치한 것으로 간주한다.
- 빗변이 축과 평행하다. 즉, 직각이등변삼각형의 빗변의 두 끝점의 좌표가 같다. 이는 다음 그림과 같이 직각이 빗변의 위쪽에 있는 직각이등변삼각형과 직각이 빗변의 아래쪽에 있는 두 종류의 직각이등변삼각형만 조건을 만족함을 의미한다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
예를 들어, 다음 그림과 같이 개의 점 , , , , 이 주어졌다고 하자. 점은 크기를 갖지 않으나, 그림에서는 편의를 위해 점을 원으로 표현하였다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
직각이 빗변의 위쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 이다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
직각이 빗변의 아래쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 이다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
두 직각이등변삼각형 중 빗변의 길이가 짧은 것은 직각이 빗변의 위쪽에 있는 경우이므로 이 구하고자 하는 길이가 된다.
제약 조건
- 주어지는 모든 수는 정수이다.
- 인 각 에 대해,
- 주어지는 개의 점들은 모두 서로 다르다. 즉, 인 모든 에 대해 또는 이다.
부분문제
- (10점)
- (18점)
- (20점) 이고, 인 각 에 대해 이다.
- (10점)
- (4점) 인 각 에 대해 이다. 즉, 모든 점의 좌표가 서로 같다.
- (6점) 인 각 에 대해 이다.
- (10점) 주어진 조건을 모두 만족하면서 빗변의 길이가 가장 짧은 직각이등변삼각형 중 적어도 하나는 빗변의 중점이 이다.
- (22점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 정수 이 주어진다.
다음 개의 줄 중 ()번째 줄에는 두 정수 와 가 공백을 사이에 두고 주어진다.
출력 형식
첫 번째 줄에 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 출력한다. 답이 항상 정수임을 증명할 수 있다.
예제
예제 1
3 0 0 2 3 4 0
6
세 꼭짓점이 인 직각이등변삼각형이 모든 조건을 만족하며, 빗변의 길이가 으로 가장 짧다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
예제 2
2 0 0 5 2
7
모든 조건을 만족하며 빗변의 길이가 인 직각이등변삼각형은 다음과 같이 두 가지 있다.
- 세 꼭짓점이 인 삼각형
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
- 세 꼭짓점이 인 삼각형
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
예제 3
4 1 5 3 2 6 6 7 4
10