BOJ 1858 - 기울기가 가장 큰 두 점
기울기 절댓값이 가장 큰 두 점은 항상 $x$ 좌표가 인접해있다.
다음과 같은 그림을 보자.
$dx=\lvert x_2-x_1 \rvert$ 라 한다면 $1,2$ 번 점들의 라인이 더 기울기가 크기 위해선 $3$ 번 점의 $x$ 에서 $3$ 번점은 저 교점 밑이여야 하는데, 그럼 $1,3$ 번 점이 기울기가 더 커지게 되어서 $1,2$ 번의 점들의 라인이 기울기가 가장 크다는 것이 불가능하다.
그런데 위에서 볼 수 있듯이 인접한 점들끼리말고도 직선상에 세 점이상이 있으면 기울기가 동일하고 점 번호에 따라 인접하지 않은 점들도 정답이 될 수 있어 최대 기울기를 먼저 구하고 그 부분만 잘 처리해주면 된다.
Comments