Boj 20149) 선분교차3

문제

백준 20149

설명

CCW 알고리즘을 이용해 선분간의 교차판정을 내리고, 한점에서 만나는지 아니면 직선이 겹치는지 경우를 나누어 오직 한 점에서 만나는 경우만 교차점을 구해야한다.

선분 교차점을 구하는 알고리즘은 크게 두가지를 알고 있다. 하나는 직선의 방정식을 이용해서 푸는 방법이고 다른 하나는 외적값을 이용해 Lerp 를 돌리는 것이다. 위 코드는 후자의 방법을 사용한다. 원리는 외적값의 절댓값이 나뉘어진 선분의 길이와 비례한다는 것으로 간단하다. 단점으로는 두 선분이 정점을 공유하는 경우는 처리할 수 없는 문제가 있다.

r1 == 0 && r2 ==0 부분인, 같은 직선 상에 있거나 두 선분이 정점을 고유하는 경우가 까다로웠는데, 각 경우를 나누어 따로 처리하면 쉽게 해결할 수 있다. 같은 직선인지 판단하기 위해 직선의 기울기를 비교하는 식에서는 나눗셈 부분을 곱셈으로 빼두면 평행선인지 쉽게 판별할 수 있다. 같은 직선 상이라면 선분의 양 끝에서 만나는 경우 외에는 모두 선분이 겹치는 경우이다. 만약 평행선이 아니면 같은 정점이 곧 교차점이 된다.

시간 복잡도

O(\(1\))

코드

using ll = long long;
using ii = pair<ll, ll>;

ll CCW(ii a, ii b, ii c)
{
	b = { b.first - a.first, b.second - a.second };
	c = { c.first - a.first, c.second - a.second };
	return b.first * c.second - b.second * c.first;
}

inline int Norm(ll r) { return r > 0 ? 1 : r < 0 ? -1 : 0; }

int main()
{
	ii in[4];
	for (int i = 0; i < 4; i++)
		cin >> in[i].first >> in[i].second;

	ll a = CCW(in[0], in[1], in[2]);
	ll b = CCW(in[0], in[1], in[3]);
	ll c = CCW(in[2], in[3], in[0]);
	ll d = CCW(in[2], in[3], in[1]);
	
	int r1 = Norm(a) * Norm(b), r2 = Norm(c) * Norm(d);
	
	if (r1 == 0 && r2 == 0) // 같은 직선 상에 있음 혹은 한 점에서 만남
	{
		if (in[0] > in[1]) swap(in[0], in[1]);
		if (in[2] > in[3]) swap(in[2], in[3]);
		if (in[0] <= in[3] && in[2] <= in[1])
		{
			cout << 1 << endl;
			if ((in[0].first - in[1].first) * (in[2].second - in[3].second) 
				== (in[0].second - in[1].second) * (in[2].first - in[3].first)) // 평행함 
			{
				if (in[0] == in[3] && in[2] < in[1]) cout << in[0].first << ' ' << in[0].second;
				if (in[0] < in[3] && in[2] == in[1]) cout << in[1].first << ' ' << in[1].second;
			}
			else { // 한 점에서 만남
				if(in[0] == in[2] || in[0] == in[3]) cout << in[0].first << ' ' << in[0].second;
				if(in[1] == in[2] || in[1] == in[3]) cout << in[1].first << ' ' << in[1].second;
			}
		}
		else cout << 0 << endl;
	}
	else if (r1 <= 0 && r2 <= 0) // 교차함
	{
		cout << 1 << endl;
		long double alpha = (long double)abs(a) / (long double)abs(b - a);
		cout.precision(15);
		cout << in[2].first * (1 - alpha) + in[3].first * alpha << ' '
			<< in[2].second * (1 - alpha) + in[3].second * alpha;
	}
	else cout << 0; // 만나지 않음
}