[BOJ][Python] 백준 2254번 - 감옥 건설

문제 링크: https://www.acmicpc.net/problem/2254

2254번: 감옥 건설

 

 

---

문제 풀이

볼록 껍질 문제이다. 모노톤 체인 기법으로 풀었으며, 다각형 내부의 점 판정은 CCW로 간단하게 구할 수 있다.

볼록 껍질에 대한 자세한 내용은 나중에 직접 다룰 예정이다.

볼록 껍질을 만들 수 있을 때까지 반복문을 돌려주고, 먼저 가장 먼 외각의 볼록 껍질이 완성된다. Px, Py의 좌표(점을 $P_{xy}$라고 하자.)와 만들어진 볼록 껍질로 다시 반복문을 돌린다. 이때 CCW를 이용하며, $P_{xy}$, $C_i$, $C_j$($C_i$, $C_j$는 임의의 연속된 볼록껍질의 점) 점 3개 모두가 반시계 방향이여야만 안의 점이므로 하나라도 시계 방향이라면 즉시 반복문을 종료하고 이후에 볼록 껍질을 만들어도 외각의 볼록 껍질 밖에 점이 있으므로, 볼록 껍질 만드는 반복문도 종료한다.

만약 볼록 껍질이 만들어지고 내부의 점이라면 개수에 +1을 해주자. 또한 모든 점에서 볼록 껍질이 만들어진 점을 빼려고 set을 이용하여 차집합하여 빼줬다.

 

 

코드

	import sys
	input = sys.stdin.readline
	def ccw(t1, t2, t3):
	x1, y1 = t1
	x2, y2 = t2
	x3, y3 = t3
	s = (x2-x1)*(y3-y1)-(y2-y1)*(x3-x1)
	if s > 0:
	return True
	else:
	return False
	n, px, py = map(int, input().split())
	pxy = (px, py)
	dots = []
	for _ in range(n):
	dots.append(tuple(map(int, input().split())))
	convex_hull_possible = True
	count = 0
	while convex_hull_possible and len(dots) > 2: #컨백스 헐 만들수 있을 때 까지 수행
	dots.sort() # 좌표 정렬
	bch, tch = [], [] #25줄부터 58줄까지 컨백스 헐 만들기(모노톤 체인)
	bch.append(dots[0])
	bch.append(dots[1])
	for i in range(2, n):
	bch.append(dots[i])
	p = True
	while p and len(bch) > 2:
	d1 = bch.pop()
	d2 = bch.pop()
	if ccw(bch[-1], d2, d1):
	bch.append(d2)
	bch.append(d1)
	p = False
	else:
	bch.append(d1)
	tch.append(dots[-1])
	tch.append(dots[-2])
	for i in range(n-3, -1, -1):
	tch.append(dots[i])
	p = True
	while p and len(tch) > 2:
	d1 = tch.pop()
	d2 = tch.pop()
	if ccw(tch[-1], d2, d1):
	tch.append(d2)
	tch.append(d1)
	p = False
	else:
	tch.append(d1)
	bch.pop()
	convex_hull = bch+tch
	dots = list(set(dots) - set(convex_hull))
	n = len(dots)
	for i in range(len(convex_hull)-1): # 점 3개를 이용하여(px, py를 포함) px, py가 밖의 점인지 안의 점인지 확인
	if not ccw(convex_hull[i], convex_hull[i+1], pxy):
	convex_hull_possible = False
	break
	if convex_hull_possible: # 안에 있는 점이라면 개수 추가 아니면 반복문까지 종료
	count += 1
	print(count)

view raw 2254.py hosted with ❤ by GitHub