[백준 문제 C++] 17386 선분 교차 1

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

17386번: 선분 교차 1

#include <stdio.h>

bool CrossCheck(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
    //중심점을 구하고 해당 점으로부터의 방향을 외적을 이용하여 찾아낸다.
    int baseX = ax1 - ax2;
    int baseY = ay1 - ay2;
    int x1 = bx1 - ax2;
    int x2 = bx2 - ax2;
    int y1 = by1 - ay2;
    int y2 = by2 - ay2;

    //백만 * 백만이 될 수 있어 정수형은 오버플로우 될 수 있다.
    long long cross1 = (long long)baseX * y1 - (long long)baseY * x1;
    long long cross2 = (long long)baseX * y2 - (long long)baseY * x2;

    if (cross1 == 0 || cross2 == 0) //같은 위치에 점이 있는 경우!
    {
        return 0; //교차로 할거면 1, 여기선 아니라고 해두었다.
    }

    if ((cross1 > 0 && cross2 > 0) ||
        (cross1 < 0 && cross2 < 0))   //중심점을 기준으로 양쪽이 같은 방향이면 교차x
    {
        return 0;
    }

    return 1;
}

int main()
{
    int ax1, ax2, ay1, ay2, bx1, bx2, by1, by2;
    int cross;
    
    scanf("%d %d %d %d", &ax1, &ay1, &ax2, &ay2);
    scanf("%d %d %d %d", &bx1, &by1, &bx2, &by2);

    cross = CrossCheck(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2);
    if (cross > 0) //성공하면 중심점을 바꿔서 한번 더 해본다.
    {
        cross = CrossCheck(bx1, by1, bx2, by2, ax1, ay1, ax2, ay2);
    }

    printf("%d\n", cross);
}

수학 관련된 문제..

벡터의 외적을 통해 방향을 알아내는 식으로 작성된 코드이다.

외적은 다음과 같은 행렬의 여인수(cofactor) 전개를 통해서 구할 수 있다.

 

아래처럼 일단 외적 계산을 위한 행렬을 배치해보자.

E1 = (1, 0, 0), E2 = (0, 1, 0), E3 = (0, 0, 1)

 

E1 E2 E3

x1 y1 z1

x2 y2 z2

 

2차원 공간이기 때문에 z1과 z2는 무조건 0이다!

그렇기 때문에 행렬식을 전개해보면 다음과 같이 된다.

 E1 * ( y1 * z2(0) - z1(0) * y2 ) = 0

-E2 * ( x1 * z2(0) - z1(0) * x2 ) = 0

 E3 * ( x1 * y2 - y1 * x2 ) = ??

 

즉 x1 * y2 - y1 * x2 계산을 통해 외적을 구할 수 있게 된다.

중심 선을 기준으로 오른쪽에 위치하면 마이너스가 나오게 되고,

왼쪽에 위치하면 플러스가 나오고 겹쳐 있다면 0이 나온다.

확인을 해보도록 하자!

위의 CrossCheck 코드를 보면

먼저 baseX, baseY 를 구하고 있다. 어느 지점을 기준으로 왼쪽 오른쪽을 판별할지를 결정하는 것이고,

특정한 점을 기준으로 좌표를 계산해주고 있다. (코드는 (3, 3) ax2, ay2 를 기준으로 삼고 있다.)

위의 그림의 경우는 (3, 3)이 중심이 된다고 가정하면

(1, 1) => (1, 1) - (3, 3) = (-2, -2)

(3, 5) => (3, 5) - (3, 3) = (0, 2)

(4, 3) => (4, 3) - (3, 3) = (1, 0)

이 된다. 이러한 그림이 되는 것이고, 중심점인 빨강 선을 기준으로 외적을 구한다.

 

0, 2에 대해서 외적을 구해보면

-2 -2

0  2    ==>  (-2 * 2) - (-2 * 0) = -4

음수값이 나온다. 즉 시계 방향(오른쪽)에 위치하고 있다.

0, 1에 대해서 외적을 구해보면

-2 -2

1  0     ==>  (-2 * 0) - (-2 * 1) = 2

양수값이 나오며 시계 반대방향(왼쪽)에 위치하고 있다고 판별이 된다.

 

우선 선분이 교차할 가능성이 생겨있게 된다. 교차할 수 없는 경우는

모두 양수 또는 음수가 나온 경우이다. (cross1 > 0 && cross2 > 0) || (cross1 < 0 && cross2 < 0)

 

빨간 선을 기준으로 판별한 결과 교차할 수 있다고 나왔다.

이번엔 파란 선을 기준으로 다시 판별을 해줘야 한다.

마찬가지로 기준점을 하나 잡아 준다. 위의 코드에선 a와 b에 대해서 순서가 바뀐 것을 확인할 수 있다.

(기준 점은 빨간 선, 파란 선을 구성하는 어느 점을 선택하든 결과는 똑같다!! <- 이걸 확인해보고 싶었다 ㅎㅎ)

 

귀찮아서 대충 이런 느낌..

파란선의 방향은 아래쪽이고.. 이러한 경우는 외적 결과가 오른쪽에 2개가 있다고 나올 것이므로

두 개의 선분은 교차하지 않는다. 파란 선을 기준으로도 왼쪽, 오른쪽이 나온다면 두 선분은

교차하게 된다. 설명을 잘 못해서 너무 길어졌네.. 어쨋든 나중에도 기억하도록!!