# BOJ - 2699 - 공약수

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(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 findStartPoint(position):
x, y = -100, -100
index = -100

for i in range(len(position)):
if position[i][1] > y:
x = position[i][0]
y = position[i][1]
index = i

if position[i][1] == y:
if position[i][0] < x:
x = position[i][0]
y = position[i][1]
index = i
return index

def solution():
for _ in range(P):
position = []
for _ in range(math.ceil(N/5)):
arr = []
for i in range(len(arr) // 2):
position.append((arr[i * 2], arr[i * 2 + 1]))

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])

print(len(ccwtemp))
d = findStartPoint(ccwtemp)
for i in range(len(ccwtemp), 0, -1):
print(ccwtemp[(i + d) % len(ccwtemp)][0], ccwtemp[(i + d) % len(ccwtemp)][1])

solution()
``````

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

Categories:

Updated: