[C/C++] 백준 20149번 - 선분 교차 3

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

출력

L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다.

두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.

좌표의 절대/상대 오차는 10-9까지 허용한다.

제한

• -1,000,000 ≤ x1, y1, x2, y2, x3, y3, x4, y4 ≤ 1,000,000
• x1, y1, x2, y2, x3, y3, x4, y4는 정수

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<ll, ll> pll;

ll x, y;
vector<pll> v;

void find_intersection(pll A, pll B, pll C, pll D) // 교점 구하기
{
	double px = (A.X * B.Y - A.Y * B.X) * (C.X - D.X) - (A.X - B.X) * (C.X * D.Y - C.Y * D.X);
	double py = (A.X * B.Y - A.Y * B.X) * (C.Y - D.Y) - (A.Y - B.Y) * (C.X * D.Y - C.Y * D.X);
	double p = (A.X - B.X) * (C.Y - D.Y) - (A.Y - B.Y) * (C.X - D.X);

	if (p == 0) // 평행할 때
	{
		// 교점이 하나일 때
		if (B == C && A <= C) cout << B.X << " " << B.Y << '\n';
		else if (A == D && C <= A) cout << A.X << " " << A.Y << '\n';
	}
	else // 교차할 때
	{
		double x = px / p;
		double y = py / p;

		cout << fixed;
		cout.precision(9);
		cout << x << " " << y;
	}
}

ll CCW(pll A, pll B, pll C) 
{
	ll tmp = A.X * B.Y + B.X * C.Y + C.X * A.Y;
	tmp -= B.X * A.Y + C.X * B.Y + A.X * C.Y;

	if (tmp > 0) return 1; // 반시계
	else if (tmp == 0) return 0; // 일직선
	else if (tmp < 0) return -1; // 시계방향
}

void solve(pll A, pll B, pll C, pll D)
{
	ll ans1 = CCW(A, B, C) * CCW(A, B, D);
	ll ans2 = CCW(C, D, A) * CCW(C, D, B);

	if (ans1 == 0 && ans2 == 0) // 평행 혹은 양 끝점이 접촉해 있을 때
	{
		// pair 대소비교. 첫번째 인자가 같다면 두번째 인자 비교
		if (A > B) swap(A, B);
		if (C > D) swap(C, D);
		
		if (A <= D && B >= C)
		{
			cout << 1 << '\n';
			find_intersection(A, B, C, D);
		}
		else cout << 0 << '\n';
	}
	else 
	{
		// 교차 혹은 한 점이 선분 위에 있을 때(끝점 x)
		if (ans1 <= 0 && ans2 <= 0)
		{
			cout << 1 << '\n';
			find_intersection(v[0], v[1], v[2], v[3]);
		}
		else cout << 0 << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 4; i++)
	{
		cin >> x >> y;
		v.push_back({ x,y });
	}

	solve(v[0], v[1], v[2], v[3]);
}

 

 

풀이 방법

 

<두 직선의 교점 구하는 방법>

Px= (x1*y2 - y1*x2)*(x3-x4) - (x1-x2)*(x3*y4 - y3*x4)
Py= (x1*y2 - y1*x2)*(y3-y4) - (y1-y2)*(x3*y4 - y3*x4)
p = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)

x = Px/p              y = Py/p

 

 

 

위와같이 여러 가지 경우의 수가 있으며, 이 문제를 풀면서 가장 신경을 쓴 부분은 두 선분이 평행이며 교점이 존재하는데, 교점이 하나인지 무수히 많은지 판별하는 부분이었다.

 

따라서 위의 4가지 경우에서 교점이 하나인 경우만 좌표를 출력하도록 하였다.

 

 

 

 

www.acmicpc.net/problem/20149

20149번: 선분 교차 3