루미 알고리즘

#1109실버직각이등변삼각형직각이등변삼각형

KOI 2025 1차코딩초등부 2번, 중등부 1번출제 정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

직각이등변삼각형

원제: 직각이등변삼각형

문제

2차원 평면 위에 서로 다른 NN개의 점이 있다. 1≤i≤N1 \le i \le N인 각 ii에 대해, ii번째 점의 좌표는 (xi,yi)(x_i, y_i)이다.

이등변삼각형이란, 세 변 중 길이가 같은 두 변이 있는 삼각형을 의미한다. 직각삼각형이란, 한 내각이 직각(90∘90^\circ)인 삼각형을 의미한다. 직각삼각형의 빗변이란, 직각삼각형에서 직각과 마주보는 변을 의미하며, 길이가 가장 긴 변이기도 하다.

직각이등변삼각형이란, 직각삼각형이면서 이등변삼각형인 삼각형을 의미한다. 즉, 삼각형의 한 내각이 직각이고, 빗변이 아닌 두 변의 길이가 서로 같은 삼각형을 의미한다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

다음 두 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 구하는 프로그램을 작성하라.

  • NN개의 점 (x1,y1),(x2,y2),⋯ ,(xN,yN)(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N) 모두 직각이등변삼각형의 경계(변 위)나 내부에 위치한다. 어떤 점이 직각이등변삼각형의 꼭짓점에 위치하는 경우도 경계에 위치한 것으로 간주한다.
  • 빗변이 xx축과 평행하다. 즉, 직각이등변삼각형의 빗변의 두 끝점의 yy좌표가 같다. 이는 다음 그림과 같이 직각이 빗변의 위쪽에 있는 직각이등변삼각형과 직각이 빗변의 아래쪽에 있는 두 종류의 직각이등변삼각형만 조건을 만족함을 의미한다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

예를 들어, 다음 그림과 같이 55개의 점 (0,−1)(0, -1), (2,4)(2, 4), (4,−1)(4, -1), (−1,2)(-1, 2), (3,1)(3, 1)이 주어졌다고 하자. 점은 크기를 갖지 않으나, 그림에서는 편의를 위해 점을 원으로 표현하였다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

직각이 빗변의 위쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 (1.5,4.5),(−4,−1),(7,−1)(1.5, 4.5), (-4, -1), (7, -1)인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 1111이다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

직각이 빗변의 아래쪽에 있는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것은 아래 그림과 같이 세 꼭짓점이 (2,−3),(−5,4),(9,4)(2, -3), (-5, 4), (9, 4)인 삼각형이며, 이 직각이등변삼각형의 빗변의 길이는 1414이다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

두 직각이등변삼각형 중 빗변의 길이가 짧은 것은 직각이 빗변의 위쪽에 있는 경우이므로 1111이 구하고자 하는 길이가 된다.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤100 0002 \le N \le 100\,000
  • 1≤i≤N1 \le i \le N인 각 ii에 대해, −100 000 000≤xi,yi≤100 000 000-100\,000\,000 \le x_i, y_i \le 100\,000\,000
  • 주어지는 NN개의 점들은 모두 서로 다르다. 즉, 1≤i<j≤N1 \le i < j \le N인 모든 i,ji, j에 대해 xi≠xjx_i \ne x_j 또는 yi≠yjy_i \ne y_j이다.

부분문제

  1. (10점) N≤2N \le 2
  2. (18점) N≤3N \le 3
  3. (20점) N≤50N \le 50이고, 1≤i≤N1 \le i \le N인 각 ii에 대해 −30≤xi,yi≤30-30 \le x_i, y_i \le 30이다.
  4. (10점) N≤50N \le 50
  5. (4점) 2≤i≤N2 \le i \le N인 각 ii에 대해 yi=yi−1y_i = y_{i-1}이다. 즉, 모든 점의 yy좌표가 서로 같다.
  6. (6점) 1≤i≤N1 \le i \le N인 각 ii에 대해 xi=yix_i = y_i이다.
  7. (10점) 주어진 조건을 모두 만족하면서 빗변의 길이가 가장 짧은 직각이등변삼각형 중 적어도 하나는 빗변의 중점이 (0,0)(0, 0)이다.
  8. (22점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정수 NN이 주어진다.

다음 NN개의 줄 중 ii (1≤i≤N1 \le i \le N)번째 줄에는 두 정수 xix_i와 yiy_i가 공백을 사이에 두고 주어진다.

출력 형식

첫 번째 줄에 조건을 모두 만족하는 직각이등변삼각형 중 빗변의 길이가 가장 짧은 것의 빗변의 길이를 출력한다. 답이 항상 정수임을 증명할 수 있다.

예제

예제 1

입력
3
0 0
2 3
4 0
출력
6

세 꼭짓점이 (−1,0),(2,3),(5,0)(-1, 0), (2, 3), (5, 0)인 직각이등변삼각형이 모든 조건을 만족하며, 빗변의 길이가 66으로 가장 짧다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

예제 2

입력
2
0 0
5 2
출력
7

모든 조건을 만족하며 빗변의 길이가 77인 직각이등변삼각형은 다음과 같이 두 가지 있다.

  • 세 꼭짓점이 (0,0),(7,0),(3.5,3.5)(0, 0), (7, 0), (3.5, 3.5)인 삼각형

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

  • 세 꼭짓점이 (−2,2),(5,2),(1.5,−1.5)(-2, 2), (5, 2), (1.5, -1.5)인 삼각형

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

예제 3

입력
4
1 5
3 2
6 6
7 4
출력
10

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2025년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.