백준 - 17387 선분교차2

 

해결과정

선분 교차 알고리즘이라는 것을 몰랐던 처음에는 float을 이용하여 다양한 규칙을 세우며 도전해 보았지만 너무 복잡하였고 구현하여도 실패하였다. 곰곰히 생각해 보니 이 문제는 소수를 사용하면 안되는 문제라고 판단하였고 여러 가정을 생각하다 결국에는 구글에 선분 교차 알고리즘을 검색해 보게 되었다.

 

예전에 실발끈 공식을 위해 외적을 2차원 공간에서 다루는 것을 보았었는데 이 문제또이 이를 이용하여 해결하는 문제였다 어떤 점 p1, p2, p3, p4가 있을때 p1, p2, p3 을 p1p2, p2p3벡터로 만든뒤 z는 0으로 외적을 하면 z는 서로 평행일때 0 그외에는 1 또는 -1값을 나타내는데 p1, p2 ,p3 은 1 p1, p2 , p4는 -1일 경우 p1, p2를 기준으로 p3, p4는 서로 다른 공간에 위치한다는 것이다 이를 착안하여 다시 선분이 교차한다는 의미를 보면 p1p2를 기준으로 p3, p4가 서로 다른 공간에 위치하는 동시에 p3p4를 기준으로 p1, p2가 서로 다른 공간에 위치하면 선분이 교차한다는 의미가 된다는 것을 알게되었다. 둘다 0 이 되었을 경우 두 선분이 서로 평행하다는 의미인데 그때에는 각 점의 위치를 판별해 서로 겹치는지 확인하면 된다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

ll ccw(ll x1, ll y1, ll x2, ll y2, ll x3, ll y3) {
	ll temp = x1 * y2 + x2 * y3 + x3 * y1;
	temp = temp - y1 * x2 - y2 * x3 - y3 * x1;
	if (temp > 0) return 1;
	else if (temp < 0) return -1;
	else return 0;
}

int main() {
    FAST;

    ll x1, y1, x2, y2, x3, y3, x4, y4;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

    ll ccw1 = ccw(x1, y1, x2, y2, x3, y3);
    ll ccw2 = ccw(x1, y1, x2, y2, x4, y4);
    ll ccw3 = ccw(x3, y3, x4, y4, x1, y1);
    ll ccw4 = ccw(x3, y3, x4, y4, x2, y2);
    
    if (ccw1 * ccw2 == 0 && ccw3 * ccw4 == 0) {
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
        if(x3 > x4) swap(x3, x4);
        if(y3 > y4) swap(y3, y4);

        if (x1 <= x4 && x3 <= x2 && y1 <= y4 && y3 <= y2) {
			cout << 1;
		}
        else {
			cout << 0;
		}
    }
    else {
        if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) {
            cout << 1;
        }
        else {
            cout << 0;
        }
    }

    return 0;
}

 

 

후기

처음에 직선의 방정식을 만들고 어느 위치에 있는지 판별하고 하는 방식이 잘못된 것은 아니지만 항상 더 쉬운방식을 생각해 보는 것이 좋다고 다시한번 깨닳는다