[백준/파이썬] 12781번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 12781번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
도윤이는 친구 3명과 함께 시험이 끝난 기념으로 도윤이의 집에서 놀기로 했다. 갑자기 배가 고파진 도윤이는 근처 맛 집인 PIZZA ALVOLOC에서 피자를 시켜먹기로 했다. 이 곳의 피자는 특이하게도, 보통 피자와 다르게 피자의 모양이 항상 볼록 다각형이다. 도윤이와 친구들은 피자를 네 등분해서 나눠먹기로 했다. 어떻게 나눌지 고민을 하던 중에 도윤이는 피자를 다음과 같이 나누기로 했다.
-
한 명씩 피자의 가장자리의 한 점을 선택한다. (같은 점을 선택하지 않는다.)
-
선택한 순서대로 첫 번째 점과 두 번째 점을 이어 선분을 만들고 세 번째 점과 네 번째 점을 이은 선분을 만든다.
-
만들어진 두 선분을 따라 피자를 자른다.
도윤이와 친구들은 잘라진 피자의 크기에 상관없이 네 조각으로만 나눠지면 먹기로 했다. 만약 네 조각으로 나눠지지 않는다면 도윤이와 친구들은 피자를 두고 싸우게 된다. 예를 들어 그림1의 경우에는 두 선분에 의해 피자가 네 조각으로 나뉘게 된다. …
입력 요약
입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다.
출력 요약
주어진 4개의 점으로 도윤이가 친구들과 사이좋게 피자를 나눠 먹을 수 있으면 1, 그렇지 않으면 0을 출력한다.
코드
def ccw(pos1, pos2, pos3):
x1, x2, x3 = pos1[0], pos2[0], pos3[0]
y1, y2, y3 = pos1[1], pos2[1], pos3[1]
tmp = x1*y2+x2*y3+x3*y1 - y1*x2-y2*x3-y3*x1
if tmp > 0:
return 1
elif tmp < 0:
return -1
else:
return 0
def isCross(a, b, c, d):
ab = ccw(a, b, c)*ccw(a, b, d)
cd = ccw(c, d, a)*ccw(c, d, b)
if ab == 0 and cd == 0:
if a > b:
a, b = b, a
if c > d:
c, d = d, c
return c<=b and a<=d
return ab<0 and cd<0
pos = list(map(int, input().split()))
print(1 if isCross(pos[0:2], pos[2:4], pos[4:6], pos[6:8]) else 0)
설명
핵심은 구현 관점에서 도윤이는 친구 3명과 함께 시험이 끝난 기념으로 도윤이의 집에서 놀기로 했다. 갑자기 배가 고파진 도윤이는 근처 맛 집인 PIZZA ALVOLOC에서 피자를 시켜먹기로 했다. 이 곳의 피자는 특이하게도, 보통 피자와 다르게 피자의 모양이 항상 볼록 다각형이다. …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기