# BOJ - 9240 - 로버트 후드

Updated:

import sys
import math

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

def ccw(p1, p2, p3):
v, u = getDegree(p1, p2), getDegree(p2, 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):
break
convex.pop()
convex.append(p3)
return convex

def getPointLength(p1, p2):
return math.sqrt(math.pow(p2[0] - p1[0], 2) + math.pow(p2[1] - p1[1], 2))

def rotating_calipers(position):
ret = 0
length = len(position)-1
j = 1
for i in range(length):
iNext = (i + 1) % length
while True:
jNext = (j + 1) % length
vx = position[iNext][0] - position[i][0]
vy = position[iNext][1] - position[i][1]

ux = position[jNext][0] - position[j][0]
uy = position[jNext][1] - position[j][1]

temp = (0, 0)

if ccw(temp, (vx, vy), (ux, uy)):
j = jNext
else:
break
dist = getPointLength(position[i], position[j])

if dist >= ret:
ret = dist
ans1 = position[i]
ans2 = position[j]
return getPointLength(ans1, ans2)

def solution():

position = []
for _ in range(N):
position.append((int(x), int(y)))

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)):
ccwtemp.append(temp[i])

print(rotating_calipers(ccwtemp))

solution()

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

Categories:

Updated: