문제

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

Gold II

코드 (Kotlin)

package org.example

import kotlin.math.max
import kotlin.math.min

fun main(args: Array<String>) {
    val input1: String? = readlnOrNull();
    val L1Info: List<Long> = input1!!.split(" ").map { it.toLong() }
    val input2: String? = readlnOrNull();
    val L2Info: List<Long> = input2!!.split(" ").map { it.toLong() }

    val opWithL1: Int = CCW(L1Info[0], L1Info[1], L1Info[2], L1Info[3], L2Info[0], L2Info[1]) * CCW(L1Info[0], L1Info[1], L1Info[2], L1Info[3], L2Info[2], L2Info[3])
    val opWithL2: Int = CCW(L2Info[0], L2Info[1], L2Info[2], L2Info[3], L1Info[0], L1Info[1]) * CCW(L2Info[0], L2Info[1], L2Info[2], L2Info[3], L1Info[2], L1Info[3])

    if (opWithL1 <= 0 && opWithL2 <= 0) {
        //each point lies on opposite side with both line
        //or one point lies on some line.
        //or line is on top of other line (when extended or not)
        if (opWithL1 == 0 && opWithL2 == 0) {
            if (L1Info[0] == L1Info[2] && L1Info[0] == L2Info[0] && L2Info[0] == L2Info[2]) {
                if (max(L1Info[1], L1Info[3]) < min(L2Info[1], L2Info[3])
                    || min(L1Info[1], L1Info[3]) > max(L2Info[1], L2Info[3])
                ) print(0)
                else print(1)
            } else {
                if (max(L1Info[0], L1Info[2]) < min(L2Info[0], L2Info[2])
                    || min(L1Info[0], L1Info[2]) > max(L2Info[0], L2Info[2])
                ) print(0)
                else print(1)
            }
        }
        else print(1)
    }
    else print(0) //each point lies on same side according to some specific line
}

fun CCW(p1x: Long, p1y: Long, p2x: Long, p2y: Long,p3x: Long, p3y: Long): Int {
    val res: Long = (p1x * p2y + p2x * p3y + p3x * p1y) - (p2x * p1y + p3x * p2y + p1x * p3y)
    if (res > 0) return 1;
    else if (res < 0) return -1
    else return 0
}

풀이

• 단순 선분 기울기를 활용한 로직으로 풀려고 했으나 부동소수점 오차 관련 문제로 해결을 못했다. 질문 게시판에 따르면 어떻게 해결하는 방법이 있는것 같긴 하나 다른 알고리즘을 알기 위해 시도하다가 그만둠

• CCW를 활용한다. 이 링크의 공식은 약간 틀렸다는 점만 유의하자. 개념이 틀리진 않았다. 세점을 따라 외적을 구하는 형식으로 직선 방향을 파악하는 알고리즘이다.

• 여기서는 line1, line2라는 직선을 기준으로 각각 line, line1의 서로 다른 꼭지점으로 갈 때의 CCW를 계산해봐야 한다. 같은 선분을 기준으로 다른 선분의 꼭지점으로 가는 CCW를 계산해 곱하면, 그 선분의 연장선을 경계선으로 점들이 서로 반대편에 있는지, 아니면 같은 쪽에 있는지 파악이 가능하다.

• 즉 한쪽이라도 양수가 나오는 경우, 그 선을 기준으로 했을 때 다른 선의 두 점이 한쪽 면에만 존재해서 교점이 생길 일이 없다는 것이다. 즉 일단 같은 선을 기준으로 한 CCW 값을 계산할 때 양수가 나오면 절대로 교점이 생길 일이 없다.

• 전부 음수가 나오거나, 하나는 0이고 다른 하나는 음수가 나오면 가능하다. 전자는 우리가 직관적으로 생각하는 교차의 경우고, 후자는 하나의 직선이 다른 직선 위에서 시작해가지고 뻗어나가는 형태의 경우다.

• 그럼 전부 0이 나오는 경우는? 이는 기울기가 같으면서 연장시킬 경우 서로 겹치는게 가능하다는 것이다. 그러나 연장해서 교점이 나오냐를 계산하는게 아니라 주어진 선분 범위에서 교차하는지를 확인하기 때문에 추가 검증이 필요하다. 나는 x나 y중 어느것이 동일하고 어느것이 바뀌는 값인지를 먼저 파악한 다음에, 특정 선의 두 점의 최소값보다, 다른 선의 두 점의 최대값이 더 작은 경우, 혹은 특정 선의 두 점의 최대값보다 다른 선의 두 점의 최소값이 더 큰 경우를 확인해 그러면 불가능하다고 판별, 아니면 가능하다고 판별했다. class를 쓰면 더 쉽게 가능하나 그냥 저렇게 하기로 함. 왜 그런지 의문이면 한번 그림을 그려보도록 하자.

• 이 논리 때문에 조건문을 위와 같은 상황에서 더 최적화하는 것은 힘들다.

• 그림과 함께 있는 설명은 이 블로그 참고.