[백준/정올] 2527. 직사각형 / 2568. 직사각형

www.acmicpc.net/problem/2527

2527번: 직사각형

www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1829&sca=9010&stx=%EC%A7%81%EC%82%AC%EA%B0%81%ED%98%95

JUNGOL

 

---

문제 풀이

이 문제는 가능한 경우의 수를 줄여나가면서 원하는 답을 찾아나가는 방법으로 보다 쉽게 해결할 수 있음

입력에서 사각형1(x1,y1,p1,q1)을 기준으로 하고 사각형2(x2,y2,p2,q2)와 비교해서 찾아나감. 

코드 문자의 순서대로 보다는 역순으로 나아가며 체크함.

• 공통부분이 없는 경우 : d
• 선으로 겹치는 경우 : b
• 점으로 겹치는 경우 : c
• 나머지 경우 ( 직사각형으로 겹침) : a

순으로 찾아 나감

나의 경우 아래 그림처럼 그림을 그려놓고 코드를 작성했다. (그냥하면..헷갈려용..ㅠㅠ)

• 공통부분이 없는경우
  • 사각형1이 위치한 가로 또는 세로에 사각형2가 위치하고 있지 않다면 이 둘은 공통부분이 없다. 아래 그림을 보면 더 이해가 쉽다.
  • x2> p1 또는 x1 > p2 또는 q1 < y2 또는 q2 < y1 인 경우 공통부분 없음.

• 선으로 겹치는 경우와 점으로 겹치는 경우
  • 아래 그림처럼 선으로 겹치는 경우
    • ① 사각형 1의 왼쪽 세로변과 사각형2의 오른쪽 세로변이 같은 선상에 있을 때이다. 
    • 또, ② 사각형1의 아래쪽 가로변과 사각형2의 위쪽 가로변이 같은 선상에 있어도 선으로 겹친다. (이 논리를 적용하여 선으로 겹치는 경우를 찾는다)
  • 이때, 선으로 겹치면서 다른 쪽 선도 겹치면 → 점
    • ① 번의 경우 사각형 1의 위쪽 가로변과 사각형 2의 아래쪽 가로변이 겹치거나 사각형 1의 아래쪽 가로변과 사각형2의 위쪽 가로변이 겹치가나 하면 두 사각형은 점으로 겹친다.
  • 그게 아니라면 → 선

 

 

마지막으로 이 모든 경우에 해당되지 않는다면 두 사각형은 사각형으로 겹친다.

ps. 문제를 풀다보면..오히려 IM수준의 시험이 더 어려울때가 있다는 생각도 든다..ㅠㅠ (아이디어를 생각해 내는 것이 쉽지 않다.)

---

소스코드 (python)

for i in range(4):
    x1,y1,p1,q1,x2,y2,p2,q2 = map(int,input().split())
    # print(x1,y1,p1,q1,x2,y2,p2,q2)
    result = "a"    #초기 설정을 a로 두고 밑에서 조건에 해당안하면 그대로 a
    if q1 < y2 or q2 < y1 or x1 > p2 or p1 <x2: #겹치지 않으면 : d
        result = "d"
    #각 면에 대해서 검사해서 점인지 선인지 확인
    if p1 == x2:    #일단 한면이 겹치는지 확인
        result = "c" if (q1 == y2 or y1 == q2) else "b"     # 꼭지점이면 점, 아니면 선
    if x1 == p2:
        result = "c" if (y1 == q2 or q1== y2) else "b"
    if q1 == y2:
        result = "c" if (p1 == x2 or p2== x1) else "b"
    if q2 == y1:
        result = "c" if (p1 == x2 or p2== x1) else "b"
    #여기 까지 왔는데..if 안걸렸으면 a
    print(result)