백준 6439 교차 C++

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

사각형과 선분의 교차 여부를 판단해주면 된다.

사각형 정점의 입력이 두 점이 주어지는데, 위치가 정해져있지 않다. x, y좌표들을 적절하게 대소비교해서 정점 네개를 잡아서

사각형을 만들어줘야 한다.

한 점만 공유해도 교차하는 것으로 간주한다고 했기 때문에, ccw 결과에 0을 포함시켜도 좋다.

사각형의 네 변과 선분을 각각 교차판정 해주고, 사각형의 내부에 선분이 존재하는지 확인한다.

#include<iostream>
#include<algorithm>
 
using namespace std;
typedef long long ll;
struct PT {
    ll x, y;
};
 
int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
    ll ret = (x1*y2 + x2 * y3 + x3 * y1) - (y1*x2 + y2 * x3 + y3 * x1);
    if (ret < 0) return -1;
    else if (ret > 0) return 1;
    else return 0; //일직선 상에 위치
}
 
bool isCross(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) {
    if (ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) <= 0 &&
        ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) <= 0) {
        //아예 멀리 떨어져 있는 경우
        if ((x1 < x3 && x1 < x4 && x2 < x3 && x2 < x4) ||
            (x3 < x1 && x3 < x2 && x4 < x1 && x4 < x2)) return false;
        if ((y1 < y3 && y1 < y4 && y2 < y3 && y2 < y4) ||
            (y3 < y1 && y3 < y2 && y4 < y1 && y4 < y2)) return false;
        return true;
    }
    return false;
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        PT l1, l2, r1, r2, r3, r4;
        cin >> l1.x >> l1.y >> l2.x >> l2.y;
        ll tmpx1, tmpx2, tmpy1, tmpy2;
        cin >> tmpx1 >> tmpy1 >> tmpx2 >> tmpy2; //사각형 좌표는 의미없는 순서로 들어옴
 
        r1 = { min(tmpx1, tmpx2), min(tmpy1, tmpy2) }; 
        r2 = { min(tmpx1, tmpx2), max(tmpy1, tmpy2) };
        r3 = { max(tmpx1, tmpx2), min(tmpy1, tmpy2) };
        r4 = { max(tmpx1, tmpx2), max(tmpy1, tmpy2) };
 
        if (isCross(l1.x, l1.y, l2.x, l2.y, r1.x, r1.y, r2.x, r2.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r2.x, r2.y, r4.x, r4.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r4.x, r4.y, r3.x, r3.y) ||
            isCross(l1.x, l1.y, l2.x, l2.y, r3.x, r3.y, r1.x, r1.y)) {
            cout << "T" << '\n'; //하나라도 교차하면
        }
        else {
            //내부에 있거나 안만나거나 (isCross false)
            if ((r1.x < l1.x && r1.x < l2.x && l1.x < r3.x && l2.x < r3.x) &&
                (r1.y < l1.y && r1.y < l2.y && l1.y < r4.y && l2.y < r4.y)) {
                cout << "T" << '\n'; //사각형의 내부에 선분이 존재해서 만나지 않은 경우
            }
            else
                cout << "F" << '\n';
        }
    }
    return 0;
}

복습

//좌표값 -> 정수이면서 크기 조건이 없음
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
struct POT {
    ll x, y;
    POT operator - (POT a) { return{x-a.x, y-a.y}; }
};
 
ll ccw(POT p1, POT p2) {
    ll ret = p1.x*p2.y - p1.y*p2.x;
    if (ret == 0) return 0;
    else if (ret > 0) return 1;
    else return -1;
}
 
ll ccw(POT p1, POT p2, POT p3) {
    return ccw(p2 - p1, p3 - p1);
}
bool isCross(POT p1, POT p2, POT p3, POT p4) {
    if (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
        ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0) {
        if ((p1.x < p3.x && p1.x < p4.x && p2.x < p3.x && p2.x < p4.x) ||
            (p3.x < p1.x && p3.x < p2.x && p4.x < p1.x && p4.x < p2.x)) return false;
        if ((p1.y < p3.y && p1.y < p4.y && p2.y < p3.y && p2.y < p4.y) ||
            (p3.y < p1.y && p3.y < p2.y && p4.y < p1.y && p4.y < p2.y)) return false;
        else
            return true;
    }    
    return false; //둘다 0이하 아니면 안 만남
}
 
int main(void) {
    int T;
    cin >> T;
    while (T--) {
        POT st, en;
        cin >> st.x >> st.y >> en.x >> en.y;
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        ll xmin, xmax, ymin, ymax;
        xmin = min(x1, x2);
        ymin = min(y1, y2);
        xmax = max(x1, x2);
        ymax = max(y1, y2);
        
        POT p[5];
        p[0] = { xmin, ymin };
        p[1] = { xmax, ymin };
        p[2] = { xmax, ymax };
        p[3] = { xmin, ymax };
        p[4] = p[0];
 
        //1. 교차하면 T
        bool endFlag = false;
        for (int i = 0; i < 4; i++)
            if (isCross(st, en, p[i], p[i + 1])) {
                cout << "T" << '\n';
                endFlag = true;
                break;
            }
        if (endFlag) continue;
 
        //2. 교차하지 않았으나, 사각형 내부에 선분이 존재하면 T
        if ((xmin < st.x && xmin < en.x && st.x < xmax && en.x < xmax) &&
            (ymin < st.y && ymin < en.y && st.y < ymax && en.y < ymax)) {
            cout << "T" << '\n';
            continue;
        }
        
        //3. 나머지
        cout << "F\n";
    }
}