백준 2527번 직사각형

정보

문제 바로가기 [클릭]

난이도: Silver1

관련 개념: #수학 #기하학 #많은 조건 분기

---

조건

시간 제한	메모리 제한
1 초	128 MB

---

문제

2차원 격자공간에 두 개의 꼭짓점 좌표로 표현되는 직사각형이 있다. 직사각형은 아래와 같이 왼쪽 아래 꼭짓점 좌표 (x, y)와 오른쪽 위 꼭짓점 좌표 (p, q)로 주어진다.

이 문제에서 모든 직사각형은 두 꼭짓점의 좌표를 나타내는 4개의 정수 x y p q 로 표현된다. 단 항상 x<p, y<q 이다. 예를 들어 위 그림에 제시된 직사각형이라면 아래와 같이 표현된다.

3 2 9 8

두 개의 직사각형은 그 겹치는 부분의 특성에 따라 다음 4가지 경우로 분류될 수 있다.

먼저 두 직사각형의 겹치는 부분이 직사각형인 경우이다. 아래 그림(a)는 공통부분이 직사각형인 경우의 3가지 예를 보여준다,

그림 (a)

또는 겹치는 부분이 아래 그림 (b)와 같이 선분이 될 수도 있고, 그림 (c)와 같이 점도 될 수 있다.

그림 (b)

그림 (c)

마지막으로 아래 그림 (d)와 같이 공통부분 없이 두 직사각형이 완전히 분리된 경우도 있다.

그림 (d)

여러분은 두 직사각형의 겹치는 부분이 직사각형인지, 선분인지, 점인지, 아니면 전혀 없는 지를 판별해서 해당되는 코드 문자를 출력해야 한다.

공통부분의 특성	코드 문자
직사각형	a
선분	b
점	c
공통부분이 없음	d

---

입력

4개의 줄로 이루어져 있다. 각 줄에는 8개의 정수가 하나의 공백을 두고 나타나는데, 첫 4개의 정수는 첫 번째 직사각형을, 나머지 4개의 정수는 두 번째 직사각형을 각각 나타낸다. 단 입력 직사각형의 좌표 값은 1이상 50,000 이하의 정수로 제한된다.

---

출력

4개의 각 줄에 주어진 두 직사각형의 공통부분을 조사해서 해당하는 코드 문자를 출력파일의 첫 4개의 줄에 각각 차례대로 출력해야 한다.

---

예제 입출력 1

입력

3 10 50 60 100 100 200 300
45 50 600 600 400 450 500 543
11 120 120 230 50 40 60 440
35 56 67 90 67 80 500 600

출력

d
a
a
b

---

코드(파이썬)

for _ in range(4):
    line = list(map(int, input().split()))
    rects = list()

    for i in range(2):
        x1, y1, x2, y2 = line[i*4:(i+1)*4]
        rects.append([(x1, y1), (x1, y2), (x2, y2), (x2, y1)])
        
    # 아예 벗어난 경우
    if (rects[0][0][0] > rects[1][2][0]) or (rects[0][2][0] < rects[1][0][0]) or\
       (rects[0][0][1] > rects[1][2][1]) or (rects[0][2][1] < rects[1][0][1]):
        result = 'd'
    # 점으로 만나는 경우
    elif (rects[0][0] == rects[1][2]) or (rects[0][1] == rects[1][3]) or\
         (rects[0][2] == rects[1][0]) or (rects[0][3] == rects[1][1]):
        result = 'c'
    # 선분으로 만나는 경우
    elif (rects[0][2][0] == rects[1][0][0] or rects[0][0][0] == rects[1][2][0]) and (rects[0][2][1] > rects[1][0][1] or rects[0][0][1] < rects[1][2][1]) or\
         (rects[0][2][1] == rects[1][0][1] or rects[0][0][1] == rects[1][2][1]) and (rects[0][2][0] > rects[1][0][0] or rects[0][0][0] < rects[1][2][0]):
        result = 'b'
    else:
        result = 'a'
    
    print(result)

---

특이사항

• 좌표를 rects의 3차원 리스트로 저장해서 코드만 늘어나는 결과를 보임
• 내 코드(30,860KB, 68ms)에 비해 우수한 코드(바로가기, 30,864KB, 68ms)와 비교

  • for tc in range(4):
      x1, y1, p1, q1, x2, y2, p2, q2 = map(int, input().split())
    
      sl = max(x1, x2)
      sr = min(p1, p2)
      sb = max(y1, y2)
      st = min(q1, q2)
    
      if sl == sr and sb == st:
          print('c')
      elif (sl == sr and sb < st) or (sb == st and sl < sr):
          print('b')
      elif sl < sr and sb < st:
          print('a')
      else:
          print('d')
    
    

  • 결과적으로 같은 기능을 수행하지만 훨씬 간결한 모습을 확인할 수 있음

---

참고문헌

-