# BOJ - 7420 - 맹독 방벽

Updated:

``````import sys
import math

_PI = 3.1415926535

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 getVector(p1, p2):
return (p1[0] * p2[0] + p1[1] * p2[1])

inner = getVector((p2[0] - p1[0], p2[1] - p1[1]), (p2[0] - p3[0], p2[1] - p3[1]))
return math.acos(inner / getPointLength(p2, p1) / getPointLength(p2, p3))

def solution():

position = []
for _ in range(N):
position.append((x, 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)-1):
ccwtemp.append(temp[i])

ret = 0
length = len(ccwtemp)
for i in range(len(ccwtemp)):
ret += getPointLength(ccwtemp[i % length], ccwtemp[(i+1) % length])

for i in range(len(ccwtemp)):
theta = getRadius(ccwtemp[(i - 1) % length], ccwtemp[i%length], ccwtemp[(i + 1) % length])
ret += L * (_PI - theta)

print(round(ret))

solution()
``````

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

Categories:

Updated: