[BOJ] 6439 교차

문제: https://www.acmicpc.net/problem/6439

 

 

문제 풀이:

직사각형의 대각선 두 점으로 (a,b), (c,d)를 입력 받았을 때, 나머지 두 점은 (c,b), (a,d)가 된다.

변 4개와 직선의 ccw를 구해 교차하는지 확인하고

한 변이라도 교차하면 T를 출력하고, 다른 변은 더 이상 보지 않아도 된다.

 

주의! 선분이 직사각형의 내부에 존재할 수도 있다.

확인을 위해 직사격형과 선분에서 최소/최대 x값과 최소/최대 y값을 구하고 비교해준다.

 

 

소스코드:

typedef long long ll;
typedef pair<ll, ll> P;
ll tc, a, b, c, d,ix1,iy1,ix2,iy2;

ll ccw(P, P, P);
bool func(P p1, P p2, P p3,P p4) {
	ll ccw1 = ccw(p1, p2, p3);
	ll ccw2 = ccw(p1, p2, p4);
	ll ccw3 = ccw(p3, p4, p1);
	ll ccw4 = ccw(p3, p4, p2);

	if (ccw1 == 0 && ccw2 == 0 && ccw3 == 0 && ccw4 == 0) {
		if (min(p1.first, p2.first) > max(p3.first, p3.first) ||
			min(p1.second, p2.second) > max(p3.second, p4.second)||
			min(p3.first, p3.first)>max(p1.first, p2.first)||
			min(p3.second, p4.second)>max(p1.second, p2.second)) return false;
	}
	if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) return true;
	return false;
}
ll ccw(P p1, P p2, P p3) {
	return p1.first * p2.second + p2.first * p3.second + p3.first * p1.second - (p1.first * p3.second + p3.first * p2.second + p2.first * p1.second);
}

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

	cin >> tc;
	while (tc--) {
		cin >>ix1>>iy1>>ix2>>iy2 >> a >> b >> c >> d;
		P i1 = make_pair(ix1, iy1);
		P i2 = make_pair(ix2, iy2);
		ll minx = min(a, c);
		ll miny = min(b, d);
		ll maxx = max(a, c);
		ll maxy = max(b, d);
		ll minix = min(ix1, ix2);
		ll miniy = min(iy1, iy2);
		ll maxix = max(ix1, ix2);
		ll maxiy = max(iy1, iy2);
		if (func({ a,b }, { a,d }, i1, i2)) {
			cout << "T\n";
			continue;
		}
		if (func({ a,b }, { c,b }, i1, i2)) {
			cout << "T\n";
			continue;
		}
		if (func({ c,d }, { c,b}, i1, i2)) {
			cout << "T\n";
			continue;
		}
		if (func({ a,d }, { c,d }, i1, i2)) {
			cout << "T\n";
			continue;
		}
		if(minx<=minix&&maxix<=maxx&&miny<=miniy&&miniy<=maxy){
			cout << "T\n";
			continue;
		}
		cout << "F\n";
	}
	return 0;
}