[백준/C++] 선분 교차 2 (No. 17387)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 풀 때 단순히 연립 방정식을 이용해 풀었다.

 

연립 방정식을 만들면 교점인 x축의 좌표를 계산할 수 있는데, 이 때 x축의 분모가 0이면 평행하다는 뜻이다.

(행렬식인 det를 계산해 det가 0인지 판단하는 방법과 동일)

 

여기서 중요한 점은 기울기가 같아도 교점이 있는 경우가 있다.

 

기울기가 같은데 교점이 있다는 것은 일차함수로 바꿨을 때 겹친다는 뜻이다.

 

여기서 겹치는지 확인하는 방법은 간단하게 y절편을 기준으로 y절편 값이 같은지 확인했다.

만약 y절편이 같다면 두 선분은 하나의 일차함수에 겹치는 선분이다.

 

이후 두 선분의 x좌표를 이용해 겹치는 선분인지 검사하도록 코드를 구현했다.

 

+ 위 방법처럼 직접 구현해 푸는 방법도 있지만, 외적을 이용해 문제를 푸는 방법도 있다.

두 개의 선분을 기준으로 다른 선분의 양 끝점과 외적한 값을 비교하는 것이다.

외적 한 값의 부호가 같으면 선분을 기준으로 위, 아래쪽에 몰려 있는 모습이다.

이를 이용해 코드를 작성하면 문제를 해결 할 수 있다.

 

​

[아이디어 정리]

1. 선분을 일차 함수로 변경한 다음 기울기를 비교한다.
2. 기울기가 다르면 교점을 찾고 교점의 x좌표가 두 선분에 속해있는지 검사한다.
3. 만약 기울기가 같다면, y절편을 이용해 평행인지 같은 일차함수인지 검사하고 x좌표값 범위를 비교한다.

 

 

Code

 

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	long long x1, x2, x3, x4, y1, y2, y3, y4;
	long long tmp, x, y;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	long long ttt;
	if (x1 > x2) {
		ttt = x1;
		x1 = x2, x2 = ttt;
		ttt = y1;
		y1 = y2, y2 = ttt;
	}
	if (x3 > x4) {
		ttt = x3;
		x3 = x4, x4 = ttt;
		ttt = y3;
		y3 = y4, y4 = ttt;
	}
	tmp = (y2 - y1) * (x4 - x3) - (y4 - y3) * (x2 - x1);
	if (tmp == 0)
	{
		if ((y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)) // 기울기가 같은 경우
		{
			if (x2 - x1 == 0 && x4 - x3 == 0)
			{
				if (x2 == x3) 
				{
					if (min(y2, y1) > max(y3, y4) || max(y2, y1) < min(y3, y4)) {
						cout << 0;
					}
					else {
						cout << 1;
					}
				}
				else {
					cout << 0;
					return 0;
				}
			}
			else {
				// y절편이 같다면
				if (((x2 - x1) * y2 - (y2 - y1) * x2) * (x4 - x3) == ((x4 - x3) * y4 - (y4 - y3) * x4) * (x2 - x1)) {
					if (min(x3, x4) > max(x2, x1) || max(x4, x3) < min(x1, x2)) {
						cout << 0;
					}
					else {
						cout << 1;
					}
				}
				else {
					cout << 0;
				}
			}
		}
		else {
			cout << 0;
		}
		return 0;
	}
	else {
		if (x2 - x1 == 0) {
			if (x2<min(x3, x4) || x2>max(x3, x4)) {
				cout << 0;
				return 0;
			}
			else {
				int aaa = (x4 - x3);
				y = x2 * (y4 - y3) + y3 * (x4 - x3) - x3 * (y4 - y3);
				if (y<min(y1 * aaa, y2 * aaa) || y>max(y1 * aaa, y2 * aaa)) {
					cout << 0;
					return 0;
				}
			}
		}
		else if (x4 - x3 == 0)
		{
			if (x4<min(x2, x1) || x4>max(x2, x1)) {
				cout << 0;
				return 0;
			}
			else
			{
				int aaa = (x2 - x1);
				y = x4 * (y2 - y1) + y1 * aaa - x1 * (y2 - y1);
				if (y<min(y3 * aaa, y4 * aaa) || y>max(y3 * aaa, y4 * aaa)) {
					cout << 0;
					return 0;
				}
			}
		}
		else {
			x = (x4 - x3) * (x2 - x1) * y3 - (y4 - y3) * (x2 - x1) * x3 - (x2 - x1) * (x4 - x3) * y1 + (y2 - y1) * (x4 - x3) * x1;
			if (x<min(x1 * tmp, x2 * tmp) || x>max(x1 * tmp, x2 * tmp) || x<min(x3 * tmp, x4 * tmp) || x>max(x3 * tmp, x4 * tmp)) {
				cout << 0;
				return 0;
			}
		}
	}
	cout << 1;

	return 0;
}

 

---

방정식으로 문제를 변경해 풀었더니 구현이 힘들었다;;

 

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