SWEA 10580 전봇대(with Python)

내가 생각한 Solution

문제에서 생각해볼 점

• 전선을 두개씩 선택하는 모든 조합을 구합니다.

• 각 경우마다 교차 하는지 체크하면 됩니다.

• 위와 같이 하는 이유는 전선은 포개어 지지 않는 이상 두점에서 교차 할 수 없습니다.

• 교차 불가한 케이스는 A 전선의 양 끝점이 모두 B 전선의 양 끝점보다 높이 있는 경우입니다. (코드로 보시는게 더 직관적으로 이해가 잘 될 것 같습니다.)

코드 구현

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    info = [[] for _ in range(N)]
    for i in range(N):
        info[i] = list(map(int, input().split()))
 
    result = 0
    for i1 in range(N-1):
        for i2 in range(i1+1, N):
            l1, r1 = info[i1]
            l2, r2 = info[i2]
            # 한 끝점은 A가 더 높고 다른 한 끝점은 B가 더 높은 경우 -> 교차 
            if ((l1 > l2 and r1 < r2) or
                (l1 < l2 and r1 > r2)):
                result += 1
 
    print(f'#{tc} {result}')