# BOJ - 2254 - 감옥 건설

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):
break
convex.pop()
convex.append(p3)
return convex

def isInside(X, Y, position):
cross = 0
for i in range(len(position)):
j = (i + 1) % len(position)
if (position[i][1] > Y) != (position[j][1] > Y):
atx = (position[j][0] - position[i][0]) * (Y - position[i][1]) / (position[j][1] - position[i][1]) + position[i][0]
if X < atx:
cross += 1
return True if cross % 2 > 0 else False

def solution():
N, X, Y = map(int, sys.stdin.readline().split())
position = []
for _ in range(N):

ret = 0
while True:
if len(position) < 3: break

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: break

if not isInside(X, Y, ccwtemp):
ret -= 1

tempdata = []
for i in range(len(position)):
if position[i] not in ccwtemp:
tempdata.append(position[i])
position = tempdata
del tempdata

ret += 1

print(ret)
solution()
``````

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

Categories:

Updated: