[백준/C++] 선분 교차 3 (No. 20149)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이전에 풀었던 선분 교차 2에서 교점의 좌표만 추가된 문제다.

그렇기 때문에 이전의 코드에서 좌표를 계산하는 부분만 추가했다.

 

이전 코드에 교점이 있는 경우 그 교점의 범위가 선분의 범위에 들어오는지 체크하기 위해 교점의 좌표를 x, y로 직접 구했었다.

 

그래서 실제 교점을 찾기 위해서는 이전에 구한 x좌표, y좌표를 이용하면 된다.

여기서 주의해야할 점은 허용오차가 매우 작기 때문에 double형을 사용해야하며 부동소수점으로 인한 오차가 커지지 않도록 주의해야한다.

 

x 좌표는 구했으므로 이를 이용해

$$ y=x*(y_2-y_1)/(x_2-x_1) + y_2 - x_2*(y_2-y_1)/(x_2-x_1) $$

를 계산하고 y좌표를 구하면 교점이 구해진다.

 

추가로 선분이 평행하면서 만나는 경우도 고려해야 한다.

 

이 경우 두 선분이 한 점에서만 만나려면 한쪽 선분의 끝점과 다른 선분의 끝점이 일치해야한다.

 

그러므로 두 선분이 y축에 평행하지 않은 경우에는 한쪽 선분의 min(x) 좌표와 다른 선분의 max(x) 좌표가 같은지 비교하고 만약 같다면 한 점에서 만나는 것이다.

 

반대로 y축에 평행하면 한쪽 선분의 min(y) 좌표와 다른 선분의 max(y) 좌표가 같은지 비교하면 된다.

 

 

​

[아이디어 정리]

1. 연립방정식을 세워 교점을 구한다.
2. 만약 교점이 없다면 (평행하다면) 두 선분이 평행한지 겹치는지 검사한다.
3. 교점이 있는 경우에는 교점의 좌표를 계산해 출력한다.
4. 교점의 좌표를 출력할 때, 부동소수점으로 인한 오차가 적도록 주의해야한다.

 

 

 

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=0, y=0, aaa;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	double 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);
	cout << fixed;
	cout.precision(16);
	if (tmp == 0)
	{
		if ((y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3)) // 기울기가 같은 경우
		{
			if (x2 - x1 == 0 && x4 - x3 == 0) // y축에 평행
			{
				if (x2 == x3)
				{
					if (min(y2, y1) > max(y3, y4) || max(y2, y1) < min(y3, y4)) {
						cout << 0;
					}
					else {
						cout << 1<<"\n";
						if (min(y2, y1) == max(y3, y4)) {
							cout << x1 << " " << min(y2, y1);
						}
						else if (min(y3, y4) == max(y2, y1)) {
							cout << x1 << " " << min(y3, y4);
						}
					}
				}
				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<<"\n";
						if (x2 == x3) {
							cout << x2 << " " << y2;
						}
						else if (x1 == x4) {
							cout << x1 << " " << x1;
						}
					}
				}
				else {
					cout << 0;
				}
			}
		}
		else {
			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 (x2 - x1 == 0) {
			if (x2<min(x3, x4) || x2>max(x3, x4)) {
				cout << 0;
				return 0;
			}
			else {
				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
			{
				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;
			}
		}
	}
	double nx = double(x) / double(tmp), ny;
	cout << 1<<"\n";
	if (x4 - x3 != 0) {
		ny = nx * (y4 - y3) / double(x4 - x3) + y4 - double(x4 * (y4 - y3)) / double(x4 - x3);

	}
	else if (x2 - x1 != 0) {
		ny = nx * (y2 - y1) / double(x2 - x1) + y2 - double(x2 * (y2 - y1)) / double(x2 - x1);

	}
	cout << nx<<" " << ny << endl;
	return 0;
}

 

---

이전에 푼 방법이 애초에 교점을 고려한 방법이라 쉽게 수정할 수 있었다.

다만 부동소수점으로 인해 코드를 수정하느라 약간 시간이 걸렸다.

뭔가 풀고도 후련하지가 않네...

 

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