# BOJ - 6850 - Cows

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 getWidth(p1, p2, p3):
return(
abs((p2[0] - p1[0]) * (p3[1] - p1[1]) - (p3[0] - p1[0]) * (p2[1] - p1[1])) // 2
)

def solution():

position = []
for _ in range(N):
x, y = map(str, sys.stdin.readline().split())
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])

ret = 0
for i in range(1, len(ccwtemp) - 2):
ret += getWidth(ccwtemp[0], ccwtemp[i], ccwtemp[i+1])

print(ret // 50)

solution()
``````

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

Categories:

Updated: