[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()함수에서 교차를 확인한다.

정답 코드

	#include <iostream>
	#include <algorithm>
	using namespace std;
	using ll = long long;
	int n;
	ll p[200000], k;
	int ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
	ll res = x1 * y2 + x2 * y3 + x3 * y1 - (y1*x2 + y2 * x3 + y3 * x1);
	if (res > 0) return 1;
	else if (res < 0) return -1;
	return 0;
	}
	bool intersect(ll x1, ll y1, ll x2, ll y2, ll a1, ll a2, ll b1, ll b2) {
	int r1 = ccw(x1, y1, x2, y2, a1, a2);
	int r2 = ccw(x1, y1, x2, y2, b1, b2);
	int r3 = ccw(a1, a2, b1, b2, x1, y1);
	int r4 = ccw(a1, a2, b1, b2, x2, y2);
	int res1 = r1 * r2;
	int res2 = r3 * r4;
	if (res1 <= 0 && res2 <= 0)
	return true;
	return false;
	}
	int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n + 1; i++) {
	cin >> p[i];
	}
	cin >> k;
	if (p[1] == k) {
	cout << "T";
	return 0;
	}
	ll x = (1LL << 31) / k;
	ll y = k * x;
	for (int i = 2; i < n + 1; i++) {
	if (intersect(0, 0, x, y, i - 1, p[i - 1], i, p[i])) {
	cout << "T";
	return 0;
	}
	}
	cout << "F";
	}

view raw 15916.cpp hosted with ❤ by GitHub

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