겹치는 직사각형의 넓이를 조건문 없이 구하기

1. 문제

 

3063번: 게시판 (acmicpc.net)

3063번: 게시판

 

2. 풀이

 

좌표간 경우를 나눠서 구하려는 순간...

 

너무 많은 경우가 생겨 틀릴 가능성이 높고 어디가 틀렸는지 찾기도 어렵다

 

실제로 오답

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    x1,y1,x2,y2,x3,y3,x4,y4 = map(int,stdin.readline().split())

    a = (x2-x1) * (y2-y1)

    if x2 <= x3 or x4 <= x1:
        
        print(a)
    
    elif y2 <= y3 or y4 <= y1:
        
        print(a)
    
    elif x1 <= x3 and x2 > x3 and x2 < x4:

        if y2 <= y4 and y1 <= y3:
            
            print(a - (x2-x3)*(y2-y3))
        
        elif y2 >= y4 and y1 >= y3:
            
            print(a - (x2-x3)*(y4-y1))
        
        elif y2 <= y4 and y1 >= y3:
            
            print(a - (x2-x3)*(y2-y1))
        
        else:
            
            print(a - (x2-x3)*(y4-y3))
    
    elif x3 <= x1 and x2 <= x4:
        
        if y2 <= y4 and y3 >= y1:

            print(a - (y4-y3)*(x2-x1))
        
        elif y2 <= y4 and y1 <= y3:
            
            print(a - (y2-y3)*(x2-x1))
        
        elif y2 >= y4 and y1 >= y3:
            
            print(a - (x2-x1)*(y4-y1))
        
        else:
            
            print(0)
    
    elif x1 <= x3 and x1 <= x4 and x4 <= x2:
        
        if y2 >= y4 and y3 >= y1:
            
            print(a - (x4-x3)*(y4-y3))
        
        elif y2 <= y4 and y3 >= y1:
            
            print(a - (x4-x3)*(y2-y3))
        
        elif y2 >= y4 and y1 >= y3:
            
            print(a - (x4-x3)*(y4-y1))
        
        else:
            
            print(a - (x4-x3) * (y2-y1))
    
    else:

        if y2 <= y4 and y1 <= y3:

            print(a - (x4-x1)*(y2-y3))
        
        elif y2 >= y4 and y1 >= y3:

            print(a - (x4-x1)*(y4-y1))
        
        elif y2 <= y4 and y1 >= y3:

            print(a - (x4-x1)*(y2-y1))
        
        else:
            
            print(a - (x4-x1) * (y4-y3))

 

 

근데 겹치는 부분은 그림만 그려보면 생각보다 쉽게 찾을 수 있다

 

좌측 하단의 x좌표부터 찾아본다면..

 

 

 

?에 들어갈 값은 얼마일까? $x_{3}$ 아니면 $x_{1}$일것이다

 

오른쪽으로 갈수록 ?에 들어갈 값이 되므로 $x_{1}$과 $x_{3}$중 더 큰 값이 들어와야 한다.

 

 

비슷하게 우측 하단의 x좌표는 어떻게 찾을 수 있을까

 

왼쪽으로 갈수록 우측 하단의 좌표가 되어야한다

 

그러니까 $x_{2}$와 $x_{4}$중 더 작은 값이 되어야한다

 

 

 

y좌표도 비슷한 방식으로 찾을 수 있을 것 같다

 

아래쪽의 y좌표는 위로 가야하므로 $y_{1}$과 $y_{3}$중 더 큰 값이 될 것이고

 

위쪽의 y좌표는 아래로 가야하므로 $y_{2}$와 $y_{4}$중 더 작은 값이 될 것이다

 

 따라서 좌측의 x좌표는 max(x1,x3)이고 우측의 x좌표는 min(x2,x4)이다.

 

그러므로 가로 길이는 min(x2,x4) - max(x1,x3)이다.

 

그런데 두 직사각형이 겹치지 않으면 이 값은 음수가 된다

 

 

따라서 가로 길이는 min(x2,x4) - max(x1,x3)와 0의 max값이 된다

 

마찬가지 논리로 세로 길이는 min(y2,y4) - max(y1,y3)와 0의 max값이 된다

 

from sys import stdin

t = int(stdin.readline())

for _ in range(t):
    
    x1,y1,x2,y2,x3,y3,x4,y4 = map(int,stdin.readline().split())

    a = (x2-x1) * (y2-y1)

    b = (max(min(x2,x4) - max(x1,x3), 0)) * (max(min(y2,y4) - max(y1,y3),0))

    print(a-b)

 

 

조금이라도 그림 그려서 생각해보는 성의를 보이자