[백준 17387번 C/C++] 선분 교차 2

 

[백준 17387번 C/C++] 선분 교차 2

 

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

17387번: 선분 교차 2

---

 

해결전략

 

 

수학

기하학

선분 교차 판정

외적 Cross

행렬식

 

 

 

외적를 구할 때 사용하는 행렬식

int CCW(const Point& a, const Point& b, const Point& c)
{
	// 행렬식을 사용해서 외적 구하기
	long long result = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);

	if (result > 0) return 1;		 // CCW. 반시계 방향
	else if (result == 0) return 0;  // 일직선
	else return -1;					 // CW. 시계 방향
}

 

---

 

정답 코드

 

#include <iostream>
using namespace std;

#define x first
#define y second
using Point = pair<long long, long long>;

int CCW(const Point& a, const Point& b, const Point& c)
{
	// 행렬식을 사용해서 외적 구하기
	long long result = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);

	if (result > 0) return 1;		 // CCW. 반시계 방향
	else if (result == 0) return 0;  // 일직선
	else return -1;					 // CW. 시계 방향
}

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

	Point a, b, c, d;
	cin >> a.x >> a.y;
	cin >> b.x >> b.y;
	cin >> c.x >> c.y;
	cin >> d.x >> d.y;

	// CCW 구하기
	int ABC = CCW(a, b, c);
	int ABD = CCW(a, b, d);
	int CDA = CCW(c, d, a);
	int CDB = CCW(c, d, b);

	if (ABC * ABD == 0 && CDA * CDB == 0)
	{
		if (a > b) swap(a, b);
		if (c > d) swap(c, d);

		if (a <= d && c <= b) cout << 1;
		else cout << 0;

		return 0;
	}

	if (ABC * ABD <= 0 && CDA * CDB <= 0) cout << 1;
	else cout << 0;

	return 0;
}

 

---

 

주의 사항

 

#define x first
#define y second
using Point = pair<int, int>;

long long이 아니라 int를 사용하면 틀린다.

 

 

---

 

 

 

정답 코드 2

 

#include <iostream>
using namespace std;

struct Point
{
	bool operator<(const Point& other) const { return x < other.x || (x == other.x && y < other.y); }
	bool operator>(const Point& other) const { return other < *this; }
	bool operator<=(const Point& other) const { return !(other < *this); }
	bool operator>=(const Point& other) const { return !(*this < other); }
	long long x;
	long long y;
};

int CCW(Point a, Point b, Point c)
{
	long long result = (a.x * b.y + b.x * c.y + c.x * a.y) - (a.y * b.x + b.y * c.x + c.y * a.x);
	if (result > 0) return 1;
	if (result < 0) return -1;
	return 0;
}

int main()
{
	Point A, B, C, D;
	cin >> A.x >> A.y >> B.x >> B.y;
	cin >> C.x >> C.y >> D.x >> D.y;

	int abc = CCW(A, B, C);
	int abd = CCW(A, B, D);
	int cda = CCW(C, D, A);
	int cdb = CCW(C, D, B);

	if (abc * abd == 0 && cda * cdb == 0)
	{
		if (A > B) swap(A, B);
		if (C > D) swap(C, D);
		cout << (A <= D && C <= B);
		return 0;
	}

	cout << (abc * abd <= 0 && cda * cdb <= 0);
}

 

---

 

 

참고 영상

 

https://www.youtube.com/watch?v=iIDgR5uFy9o

 

 

 

---