BOJ - 17403 - 가장 높고 넓은 성

Updated:

``````import sys

def getDegree(p1, p2):
return p2[0] - p1[0], p2[1] - p1[1]

def ccw(p1, p2, p3):
v, u = getDegree(p1, p2), getDegree(p1, p3)
if v[0] * u[1] > v[1] * u[0]: return True
else: return False

def convex_hull(position):
convex = []

for p3 in position:
while len(convex) >= 2:
p1, p2 = convex[-2], convex[-1]
if ccw(p1, p2, p3) == 1:
break
convex.pop()
convex.append(p3)
return convex

def solution():
position = []
for _ in range(N):
check = position
ret = 0
while True:

position = sorted(position, key=lambda x:(x[0], x[1]))
ccwtemp = convex_hull(position)
position.reverse()
temp = convex_hull(position)

for i in range(1, len(temp)-1):
ccwtemp.append(temp[i])

if len(ccwtemp) < 3:
for arr in ccwtemp:
check[check.index(arr)] = -1
break

tempdata = []
for i in range(len(position)):
if position[i] not in ccwtemp:
tempdata.append(position[i])
else:
check[check.index([position[i][0], position[i][1]])] = ret
position = tempdata
ret += 1

for c in check:
try:
print(c + 1, end = ' ')
except Exception as e:
print(0, end = ' ')

solution()
``````

https://www.acmicpc.net/problem/17403

Categories:

Updated: