BOJ 6439번: 교차

반응형

입력으로 주어진 선분과 직사각형이 교차하는지를 판별하는 문제이다.

직사각형의 좌표들가 대각선으로 2개 들어오는데, x, y좌표를 각각 크기 비교해서 사용해야하는데 당연히 작은게 우선 들어올거라 판단해 여러번 틀린 문제였다.

 

이 문제는 크게 2가지 기준을 통과하면 T로 판별하게 하였다.

먼저, 직사각형 점들을 저장해주고, CCW로 선분이 직사각형 4개의 변과 교차하는지 판별해주었다.

이후, 직사각형 4개의 각 변들과 선분과의 CCW >0 이면 선분이 직사각형 내부에 있다는 뜻이므로 이 또한 T로 판별하게 해주었다.

 

 

 

#include <cstring>
#include <cstdio>
using namespace std;
 
#define ll long long
struct MY {
    ll x, y;
};
MY my[4];
int maxx(int a, int b) {    return a > b ? a : b;}
int minn(int a, int b) {    return a < b ? a : b;}
 
int CCW(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
    ll tmp = x1 * y2 + x2 * y3 + x3 * y1;
    tmp -= (y1 * x2 + y2 * x3 + y3 * x1);
    if (tmp < 0)
        return -1;
    if (tmp > 0)
        return 1;
    return 0;
}
bool isoverlapped(ll l1x1, ll l1y1, ll l1x2, ll l1y2, ll l2x1, ll l2y1, ll l2x2, ll l2y2) {
    if (maxx(l1x1, l1x2) < minn(l2x1, l2x2))
        return false;
    if (minn(l1x1, l1x2) > maxx(l2x1, l2x2))
        return false;
    if (maxx(l1y1, l1y2) < minn(l2y1, l2y2))
        return false;
    if (minn(l1y1, l1y2) > maxx(l2y1, l2y2))
        return false;
    return true;
}
bool iscrossed(ll l1x1, ll l1y1, ll l1x2, ll l1y2, ll l2x1, ll l2y1, ll l2x2, ll l2y2) {
    int chk1 = CCW(l1x1, l1y1, l1x2, l1y2, l2x1, l2y1)*CCW(l1x1, l1y1, l1x2, l1y2, l2x2, l2y2);
    int chk2 = CCW(l2x1, l2y1, l2x2, l2y2, l1x1, l1y1)*CCW(l2x1, l2y1, l2x2, l2y2, l1x2, l1y2);
    if (chk1 == 0 && chk2 == 0) {
        return isoverlapped(l1x1, l1y1, l1x2, l1y2, l2x1, l2y1, l2x2, l2y2);
    }
    return chk1 <= 0 && chk2 <= 0;
}
int main()
{
    register int t, i, j;
    int T;
    ll xs, ys, xe, ye, xl, yt, xr, yb;
    bool flag = false;
 
    scanf("%d", &T);
    for(t = 1; t <= T; t++) {
        scanf("%lld %lld %lld %lld %lld %lld %lld %lld", &xs, &ys, &xe, &ye, &xl, &yt, &xr, &yb);
        ll x1 = minn(xl, xr);
        ll y1 = minn(yt, yb);
        ll x2 = maxx(xl, xr);
        ll y2 = maxx(yt, yb);
        //직사각형 선분들 저장
        my[0].x = x1;
        my[0].y = y1;
        my[1].x = x2;
        my[1].y = y1;
        my[2].x = x2;
        my[2].y = y2;
        my[3].x = x1;
        my[3].y = y2;
 
        //선분이 교차하는지 판단
        flag = false;
        for (i = 0; i < 4; i++) {
            if (iscrossed(my[i].x, my[i].y, my[(i + 1) % 4].x, my[(i + 1) % 4].y, xs, ys, xe, ye) == true) {
                flag = true;
            }
        }
        //선분이 도형안에 포함되 있는지 판단
        int isinternal = 0;
        for (i =0; i < 4; i++) {
            if ((CCW(my[i].x, my[i].y, my[(i + 1)%4].x, my[(i + 1) % 4].y, xs, ys) > 0) && (CCW(my[i].x, my[i].y, my[(i + 1) % 4].x, my[(i + 1) % 4].y, xe, ye) > 0)) {
                isinternal++;
            }
        }
        printf("%c\n", (flag==true || isinternal==4) ? 'T' : 'F' );
    }
    return 0;
}