20149번: 선분 교차 3 - CCW

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

20149번: 선분 교차 3

 

선분 교차와 CCW 간의 관계는 참조 링크의 포스팅을 참조하면 된다.

선분이 일직선으로 겹칠 때(coincide), 주어진 점이 동일할 때(dotAndDot), 교차할 때(cross), 겹치지 않을 때를 구분해서 문제를 풀어야만 한다.

교차할 때, 겹치지 않을 때는 큰 문제가 되지 않았지만, 일직선으로 겹칠 때, 주어진 점이 동일할 때 어떻게 조건문을 만들어야 하는지 애먹었던 문제였다.

#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>
#include <string>
#include <iomanip>
using namespace std;

typedef long double ld;
typedef pair<int, int> pii;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ld x1, y1, x2, y2, x3, y3, x4, y4;
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

	ld p2p1x = x2 - x1; ld p2p1y = y2 - y1;
	ld p2p3x = x2 - x3; ld p2p3y = y2 - y3;
	ld p2p4x = x2 - x4; ld p2p4y = y2 - y4;

	ld p4p3x = x4 - x3; ld p4p3y = y4 - y3;
	ld p4p1x = x4 - x1; ld p4p1y = y4 - y1;
	ld p4p2x = x4 - x2; ld p4p2y = y4 - y2;

	ld ccw1 = p2p1x * p2p3y - p2p1y * p2p3x;
	ld ccw2 = p2p1x * p2p4y - p2p1y * p2p4x;
	ld ccw3 = p4p3x * p4p1y - p4p3y * p4p1x;
	ld ccw4 = p4p3x * p4p2y - p4p3y * p4p2x;

	bool cross{ true };
	bool coincide{ false };
	bool dotAndDot{ false };
	int dot1, dot2;
	if ((ccw1 < 0 && ccw2 < 0) || (ccw1 > 0 && ccw2 > 0)) cross = false;
	if ((ccw3 < 0 && ccw4 < 0) || (ccw3 > 0 && ccw4 > 0)) cross = false;
	if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0)
	{
		if (max(x1, x2) < min(x3, x4)) cross = false;
		if (min(x1, x2) > max(x3, x4)) cross = false;
		if (max(y1, y2) < min(y3, y4)) cross = false;
		if (min(y1, y2) > max(y3, y4)) cross = false;
		
		if (min(x1, x2) < max(x3, x4) && max(x1, x2) > min(x3, x4)) coincide = true;
		if (min(y1, y2) < max(y3, y4) && max(y1, y2) > min(y3, y4)) coincide = true;
	}

	if ((x1 == x3 && y1 == y3) || (x1 == x4 && y1 == y4))
	{
		dotAndDot = true;
		dot1 = x1; dot2 = y1;
	}
	else if((x2 == x3 && y2 == y3) || (x2 == x4 && y2 == y4))
	{
		dotAndDot = true;
		dot1 = x2; dot2 = y2;
	}
	
	cout << cross << "\n";
	if (cross && !coincide)
	{
		if (dotAndDot) cout << dot1 << " " << dot2;
		else
		{
			cout << fixed << setprecision(16);
			cout << ((x2 - x1) * (x4 * y3 - x3 * y4) - (x4 - x3) * (x2 * y1 - x1 * y2))
				/ ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3)) << " "
				<< ((y2 - y1) * (y4 * x3 - y3 * x4) - (y4 - y3) * (y2 * x1 - y1 * x2))
				/ ((y4 - y3) * (x2 - x1) - (y2 - y1) * (x4 - x3));
		}
	}
}

 

참조 링크

https://anz1217.tistory.com/105

CCW