[BOJ] 백준 15916 가희는 그래플러야!!

문제 링크

https://www.acmicpc.net/problem/15916

평면 위의 점들을 이은 그래프와 한 직선 $y = kx$가 주어졌을 때 $(0, 0)$이외의 점에서 한 번이라도 직선과 그래프가 만나는지를 확인하면 된다. CCW를 이용해 선분의 교차를 확인하자.

우선 직선과 선분의 교차 여부를 판단하기는 어려우니, 선분과 선분의 교차 여부를 확인하기 위해 $y = kx$를 선분으로 만든다. 평면 위 점들의 y좌표가 $0 \leq y \leq 2^{30}$ 이므로 직선 위의 점 중 $y' > 2^{30}$ 를 만족하는 적당한 점$(x',\ y')$와 $(0, 0)$을 이어 선분으로 만들면 된다. 

$x' = \dfrac{2^{31}}{k}$ 

$y' = kx'$ 정도가 좋겠다.

수학적 나눗셈이 아닌 정수형 나눗셈임을 상기하자.

단, $k = 0$인 경우 $k$로 나눌 수 없으나 이 상황에서는 그래프와 직선이 겹치지 않는게 자명하다.

따라서 바로 F를 출력하고 종료하도록 한다.

교차를 판별하기 전에 확인해야 할 게 있다.

제 1사분면에서 그래프의 첫 번째 선분은 $(0, 0)$을 포함하고, 직선 $y = kx$ 또한 $(0, 0)$을 포함한다. 따라서 $[0, 1]$ 구간은 두 선분이 항상 $(0, 0)$에서 교차하기 때문에 다른 방법으로 교차를 확인해야 한다.

다음 그림을 보자.

구간 $[0, 1]$에서는 위의 세가지 경우만 나올 수 있는데, $k = y[1]$인 경우에만 교차함을 알 수 있다.

해당 구간만 확인하면 뒷쪽은 CCW로 교차를 판단할 수 있다.

CCW는 https://degurii.tistory.com/47 여기 자세히 설명되어있다.

아래 코드는 bool intersect()함수에서 교차를 확인한다.

정답 코드

질문, 피드백 환영합니다.