두 정사각형이 차지하는 넓이를 구하기

알고리즘

두 정사각형이 차지하는 넓이를 구하기

kjyook 2023. 5. 31. 16:55

728x90

문제

한 변의 길이가 같은 두 개의 정사각형이 주어집니다. 이 정사각형들은 가장 왼쪽 위의 점의 좌표 (a, b)와 (c, d), 그리고 한 변의 길이 r로 표현할 수 있으며, 정사각형의 각 변들은 X축 또는 Y축에 평행합니다. 이 정사각형들은 겹칠 수도 있고, 겹치지 않을 수도 있습니다.

두 정사각형 왼쪽 위 좌표 (a, b)와 (c, d), 두 정사각형의 변의 길이인 r이 매개변수로 주어질 때, 이 두 정사각형이 차지하는 면적을 출력하는 프로그램을 작성하시오.

제한사항

0 ≤ a ≤ 1,000,000
0 ≤ b ≤ 1,000,000
0 ≤ c ≤ 1,000,000
0 ≤ d ≤ 1,000,000
1 ≤ r ≤ 500,000

입출력 예

a	b	c	d	r	result
1	2	1	2	3	9
1	2	4	2	3	18
2	5	0	3	3	17

입출력 예 설명

입출력 예 #1
두 정사각형의 왼쪽 위 꼭짓점이 (1, 2)에 위치하고 한 변의 길이가 3이므로 차지하는 면적은 9입니다.

입출력 예 #2
첫 번째 정사각형은 (1, 2)에 위치하고 두 번째 정사각형은 (4, 2)에 위치하는데 한 변의 길이가 3이므로 서로 겹치는 부분이 없습니다. 따라서 두 정사각형의 합인 9 + 9 = 18만큼의 면적을 차지합니다.

입출력 예 #3
첫 번째 정사각형은 (2, 5)에 위치하고 두 번째 정사각형은 (0, 3)에 위치합니다. 한 변의 길이가 3이므로 왼쪽 위 꼭짓점이 (2, 3)이고, 오른쪽 아래 꼭짓점이 (3, 2)인 사각형만큼 면적이 겹칩니다. 따라서 두 정사각형의 넓이에서 겹치는 면적만큼 뺀 9 + 9 - 1 = 17만큼의 면적을 차지합니다.

풀이

사각형의 왼쪽 위의 점과 한 변의 길이를 입력받으면 두 정사각형이 어떤 관계를 가지는지 알아야 한다. 만나는지 안 만나는지를 판단해야 한다. 만나지 않는다면 두 정사각형이 차지하는 넓이는 (r^2)*2가 될 것이고, 두 정사각형이 만난다면 (r^2)*2 - (겹치는 넓이) 만큼의 넓이를 차지할 것이다.

하나의 사각형의 넓이를 구하는건 너무나도 쉽다. -> r^2 하면 나오기 때문이다. 어려운 부분은 겹치는 영역을 구하는 일인데, 만약 겹친다고 가정하면 겹치는 영역은 직사각형 모양일 것이다. ( 직선인 경우는 겹치지 않는다고 판단한다. 왜냐하면 넓이가 0이기 때문이다. )

그래서 우리가 해야할 일은 겹치는 영역의 넓이, 즉 직사각형의 넓이를 구하면 된다. 이 영역의 넓이를 구하려면 먼저 직사각형을 구해야 하는데, 그래서 나는 입력받은 정사각형의 왼쪽 x좌표, 오른쪽 x좌표, 아래 y좌표, 위 y좌표를 각각 앞으로 left, right, top, bottom이라고 부르고, 이를 사용해 구해볼 것이다.

예를 들어 (a, b) = (2, 7), (c, d) = (4, 5), r = 3을 입력받으면 아래 그림과 같은 상황이 된다.

초록색 영역이 겹치는 직사각형이 될 것이다. ( 이 경우에는 직사각형이 아닐 수 있지만 보통은 직사각형이다. )

겹치는 영역을 따로 표시해보면 다음과 같다.

이 직사각형의 넓이를 구하는 것은 너무나도 쉽다. 가로 x세로 하면 된다.

그래서 나는 이 직사각형을 구하는 방법으로 두 정사각형의 left와 bottom에서 큰 값이 새로운 도형의 left와 bottom값이 되고, 두 정사각형의 right와 top에서 작은 값이 새로운 도형의 right와 bottom 값이 될 것이다.

이렇게 해서 만들어진 새로운 도형은 두 정사각형의 겹치는 영역을 표시할 것이고, left >= right or bottom >= top이라면 직사각형이 아니므로 겹치는 영역이 없는 것이다.

코드

사각형을 class를 통해 하나하나 구현을 해야하나 고민해 봤는데 넓이만 구하면 되는 경우인 거 같아서 굳이 구현하지 않았다. 겹치는 영역의 left, right, bottom, top을 구하여 이 도형이 사각형이라면 ( left < right and bottom < top ) 두 정사각형 넓이의 합에서 해당 영역만큼의 넓이를 뺀 값을 출력하고, 도형이 사각형이 아니라면 넓이가 0 이므로 두 정사각형의 넓이의 합을 출력해 준다.

import sys

def main():
    a,b,c,d,r = map(int,sys.stdin.readline().split())
    left = max(a,c)
    right = min(a+r,c+r)
    bottom = max(b-r,d-r)
    top = min(b,d)
    
    #입력받은 값이 주어진 갑의 범위가 맞는지 확인
    if a<0 or b<0 or c<0 or d<0 or r<0 or a>1000000 or b>1000000 or c>1000000 or d>1000000 or r>500000:
        print("잘못된 입력입니다.")
        return

    if left>=right or bottom>=top:
        print(r*r*2)
    else:
        print(r*r*2 - (right - left)*(top - bottom))

if __name__=="__main__":
    main()

728x90

저작자표시