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

문제

• 선분 교차 2(백준17387)

풀이

문제 해석을 하자면,

• 두 직선이 교차하는지 판별하는 문제

풀이

• 조건부분에 “한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것” 고려해줘야 한다.
• 이 때문에 꼭, 같은 직선상에 존재하는 두 직선의 교차 여부도 예외로 처리할 것(between함수 활용)
• 추가로 long long 타입으로 계산할 것. int형은 범위에 한계가 있음.
  • 행렬식 계산 때문에 최대 범위가 1,000,000^4
  • long long으로도 범위 문제가 있으면 double 사용

코드

#include<iostream>
using namespace std;

struct point {
	long long x; long long y;
};
typedef point Point;

long long ccw2(Point p, Point q) {
	return p.x * q.y - p.y * q.x;
}

long long ccw(Point r, Point p, Point q) {
	// r만큼 빼서 원점으로 이동 (ccw2 계산 위해)
	p.x -= r.x;
	p.y -= r.y;
	q.x -= r.x;
	q.y -= r.y;
	return ccw2(p, q);
}

int direction(Point a, Point b, Point c) {
	if (ccw(a, b, c) > 0) return 1;
	if (ccw(a, b, c) < 0) return -1;
	if (ccw(a,b,c) == 0) return 0;
}

// 점 c가 a,b직선 상에 존재하는지 판별함수
bool between(Point a, Point b, Point c) {
	// 1. 일직선 상에 존재하나 확인
	if (ccw(a, b, c) != 0) return false;
	else {
		// 2. 수직 여부 확인 후 범위제한
		if (a.x == b.x) {
			if ((c.y >= a.y && c.y <= b.y) || (c.y >= b.y && c.y <= a.y)) return true;
		}
		else {
			if ((c.x >= a.x && c.x <= b.x) || (c.x >= b.x && c.x <= a.x)) return true;
		}
		return false;
	}
}

int interection(Point a, Point b, Point c, Point d) {
	// (a,b,c)*(a,b,d) ==-1 && (c,d,a)*(c,d,b)==-1 성립하면 교차
	// 추가조건 때문에 <=0로 판별
	if (direction(a, b, c) * direction(a, b, d) <= 0 && direction(c, d, a) * direction(c, d, b) <= 0) {
		// direction함수는 방향만을 나타내기 때문에 만약 0인 경우 일직선상인 건데,
		// 두 직선이 서로 접하는지 범위제한을 줘서 판단할 필요가 있음(between 함수 활용)
		if (direction(a, b, c) * direction(a, b, d) == 0 && direction(c, d, a) * direction(c, d, b) == 0) {
			// 점 c또는 d가 a,b직선 상에 존재하나 판단
			// 점 a또는 b가 c,d직선 상에 존재하나 판단
			if (between(a, b, c) || between(a, b, d)|| between(c, d, a) || between(c, d, b)) {
				return 1;
			}
			else
				return 0;
		}
		return 1;
	}
	else 
		return 0;
}

Point inPoint[4];

int main() {
	// input
	for (int i = 0; i < 4; i++) {
		cin >> inPoint[i].x >> inPoint[i].y;
	}
	
	// run && output
	cout << interection(inPoint[0], inPoint[1], inPoint[2], inPoint[3]);


	return 0;
}

느낀점

생략