Problem:


Convex Hull

Find the convex hull of a given set of points P. In other words, find the smallest convex polygon containing all the points of P. Here, in a convex polygon, all interior angles are less than or equal to 180 degrees.

Please note that you should find all the points of P on both corner and boundary of the convex polygon.

Input

n
x1 y1 
x2 y2
:
xn yn

The first integer n is the number of points in P. The coordinate of the i-th point pi is given by two integers xi and yi. 

Output

In the first line, print the number of points on the corner/boundary of the convex polygon. In the following lines, print x y coordinates of the set of points.
The coordinates should be given in the order of counter-clockwise visit of them starting from the point in P with the minimum y-coordinate, or the leftmost such point in case of a tie.

Constraints

3 ≤ n ≤ 100000

-10000 ≤ xi, yi ≤ 10000

No point in the P will occur more than once.

Sample Input 1

7
2 1
0 0
1 2
2 2
4 2
1 3
3 3

Sample Output 1

5
0 0
2 1
4 2
3 3
1 3

Sample Input 2

4
0 0
2 2
0 2
0 1

Sample Output 2

4
0 0
2 2
0 2
0 1



Sample input:
7
2 1
0 0
1 2
2 2
4 2
1 3
3 3


Sample output:
5
0 0
2 1
4 2
3 3
1 3

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import deque

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    return cross(x, y) > 0

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and ccw(U[-1],U[-2],c[i]):
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and ccw(L[-1], L[-2], c[i]):
        L.pop()
        j -= 1
    L.append(c[i])

ans = U
for i in range(1,len(L)-1):
    x, y = L[i]
    ans.append([x,y])
print(len(ans))
for x,y in ans:
    print(x, y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import deque

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    return cross(x, y) > 0

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and ccw(U[-1],U[-2],c[i]):
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and ccw(L[-1], L[-2], c[i]):
        L.pop()
        j -= 1
    L.append(c[i])

ans = U
for i in range(1,len(L)-1):
    x, y = L[i]
    ans.append([x,y])

i = ans.index(sorted(ans, key=lambda x: (x[1],x[0]))[0])
ans = list(ans)
for x,y in ans[:i] + ans[i:]:
    print(x, y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
from collections import deque

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    return cross(x, y) > 0

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and ccw(U[-1],U[-2],c[i]):
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and ccw(L[-1], L[-2], c[i]):
        L.pop()
        j -= 1
    L.append(c[i])

ans = U
for i in range(1,len(L)-1):
    x, y = L[i]
    ans.append([x,y])

print(len(ans))
i = ans.index(sorted(ans, key=lambda x: (x[1],x[0]))[0])
ans = list(ans)
for x,y in ans[:i] + ans[i:]:
    print(x, y)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
pts = [[int(_) for _ in raw_input().split()] for i in xrange(n)]


def dot(a, b):
    return a[0] * b[0] + a[1] * b[1]


def cross(a, b):
    return a[0] * b[1] - a[1] * b[0]


def norm(a):
    return dot(a, a)


def dist2(a, b):
    return norm(sub(a, b))


def sub(a, b):
    return [a[0] - b[0], a[1] - b[1]]


# find the first point
p = min(pts, key=lambda p: (p[1], p[0]))
ans = [p]

cur = ans[0]
cur_dxdy = (-1, 0)
while True:
    # Find the next point
    q = pts[0]
    dxdy = sub(q, cur)
    d = dist2(cur, q)
    for q_ in pts[1:]:
        if q_ is cur:
            continue
        dxdy_ = sub(q_, cur)
        v = cross(dxdy, dxdy_)
        if v > 0:
            continue
        d_ = dist2(cur, q_)
        if v == 0 and d_ < d:
            continue
        q = q_
        dxdy = dxdy_
        d = d_

    # Find the points in the middle
    mids = [m for m in pts
            if cross(dxdy, sub(m, cur)) == 0 and dot(sub(m, cur), sub(m, q)) < 0]
    mids.sort(key=lambda m: dist2(cur, m))
    ans += mids

    if p is q:
        break
    ans.append(q)
    cur_dxdy = dxdy
    cur = q

print len(ans)
for p in ans:
    print p[0], p[1]

Submission status: Time Limit Exceeded

Solution code:
def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = []
for i in range(n):
    P += [[int(x) for x in input().split()]]
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = []
for i in range(n):
    P.append([int(x) for x in input().split()])
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = deque([])
for i in range(n):
    P.append([int(x) for x in input().split()])
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def isCLKWISE(ph):
    a = [ph[-1][0]-ph[-3][0],ph[-1][1]-ph[-3][1]]
    b = [ph[-2][0]-ph[-3][0],ph[-2][1]-ph[-3][1]]
    crs = a[0]*b[1] - a[1]*b[0]
    if crs < 0 :
        return False
    else :
        return True
    
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                phU.remove(phU[-2])
                if len(phU) == 2 :
                    break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) :
                break
            else :
                del phL[-2]
                if len(phL) == 2 :
                    break
    ph = phU + phL[1:-1]
    return ph

n = int(input())
P = deque([])
for i in range(n):
    P.append([int(x) for x in input().split()])
    
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
for q in Q:
    idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
    R = Q[idx:] + Q[:idx]
for r in R:
    print(r[0],r[1])

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = c[:2]

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = c[:2]

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))

first = sorted(ans,key=lambda x: (x[1], x[0]))[0]
i = ans.index(first)
for x,y in ans[i:] + ans[:i]:
    print(x, y)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import deque

h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))

first = sorted(ans,key=lambda x: (x[1], x[0]))[0]
i = ans.index(first)
for x,y in ans[i:] + ans[:i]:
    print(x, y)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import deque

def sub(a, b):
    return [a[0] - b[0],a[1] - b[1]]

def cross(a, b):
    return  a[0] * b[1] - a[1] * b[0]

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    return cross(x, y) > 0

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = deque(c[:2])

for i in range(2, n):
    j = len(U)
    while j >= 2 and ccw(U[-1],U[-2],c[i]):
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = deque(c[:2])

for i in range(2, n):
    j = len(L)
    while j >= 2 and ccw(L[-1], L[-2], c[i]):
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))

first = sorted(ans, key=lambda x: (x[1], x[0]))[0]
i = ans.index(first)
for x,y in ans[i:] + ans[:i]:
    print(x, y)

Submission status: Accepted

Solution code:
def cross(a, b):
  return a.real * b.imag - a.imag*b.real

def convex_hull(p):
  pp = sorted(p, key=lambda x:(x.imag, x.real))
  n = len(pp)
  ans = [0] * (n+1)
  j = 0

  #上側を入れていく
  for i in range(n):
    while j > 1 and cross(ans[j-1] - ans[j-2], pp[i]-ans[j-1]) < 0: #常に次の点が下側に
      j -= 1
    ans[j] = pp[i]
    j += 1
  k = j
  #下側を入れていく
  for i in range(n-2, -1, -1):
    while j > k and cross(ans[j-1]-ans[j-2], pp[i]-ans[j-1]) < 0: #常に次の点が下側に
      j -= 1
    ans[j] = pp[i]
    j +=1
  return ans[0:j-1]

n = int(input())
p=[]
for i in range(n):
  x,y = list(map(int, input().split()))
  p.append(complex(x,y))
ans = convex_hull(p)
print(len(ans))

for i in ans:
  print(int(i.real), int(i.imag))

Submission status: Accepted

Solution code:
n = int(raw_input())
pts = [complex(*[float(_) for _ in raw_input().split()]) for i in xrange(n)]


def cross(a, b):
    return (a.conjugate() * b).imag


pts.sort(key=lambda p: (p.imag, p.real))

right = []
for p in pts:
    while len(right) >= 2 and cross(right[-1] - right[-2], p - right[-1]) < 0:
        right.pop()
    right.append(p)

left = []
for p in reversed(pts):
    while len(left) >= 2 and cross(left[-1] - left[-2], p - left[-1]) < 0:
        left.pop()
    left.append(p)

ans = right[:-1] + left[:-1]
print len(ans)
for p in ans:
    print int(p.real), int(p.imag)

Submission status: Accepted

Solution code:
def cross(a, b):
    return (a.conjugate() * b).imag

points = int(raw_input())
pts = [complex(*[float(_) for _ in raw_input().split()]) for i in xrange(points)]

 
pts.sort(key=lambda p: (p.imag, p.real))
go_right = []
for p in pts:
    while len(go_right) >= 2 and cross(go_right[-1] - go_right[-2], p - go_right[-1]) < 0:
        go_right.pop()
    go_right.append(p)

go_left = []
for p in reversed(pts):
    while len(go_left) >= 2 and cross(go_left[-1] - go_left[-2], p - go_left[-1]) < 0:
        go_left.pop()
    go_left.append(p)

ans = go_right[:-1] + go_left[:-1]
print len(ans)
for p in ans:
    print int(p.real), int(p.imag)

Submission status: Accepted

Solution code:
from sys import stdin
import math
from collections import deque

EPS = 1e-10

class Vector:
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    # can't  apply "number * Vector" but "Vector * number"
    def __mul__(self, k):
        return Vector(self.x * k, self.y * k)

    def __truediv__(self, k):
        return Vector(self.x / k, self.y / k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    # usually cross operation return Vector but it returns scalor
    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def rotate(self, theta):
        return Vector(self.x * math.cos(theta)
                               - self.y * math.sin(theta),
                               self.x * math.sin(theta)
                               + self.y * math.cos(theta))

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

class Segment:
    def __init__(self, p1=Point(0, 0), p2=Point(1, 1)):
        self.p1 = p1
        self.p2 = p2

class Line(Segment):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > EPS:
        return 1
    elif a.cross(b) < -EPS:
        return -1
    elif a.dot(b) < -EPS:
        return 2
    elif a.norm() < b.norm():
        return -2
    else:
        return 0

def convex_hull(P):
    n = len(P)
    A = sorted(P, key=lambda p: (p.x, p.y))
    U = deque([])
    L = deque([])
    for i in range(n):
        if i < 2:
            U.append(A[i])
        else:
            while ccw(U[-2], U[-1], A[i]) == 1:
                U.pop()
                if len(U) == 1:
                    break
            U.append(A[i])

    for i in range(n-1, -1, -1):
        if i > n-3:
            L.append(A[i])
        else:
            while ccw(L[-2], L[-1], A[i]) == 1:
                L.pop()
                if len(L) == 1:
                    break
            L.append(A[i])

    U.pop()
    U.popleft()
    return U + L

def read_polygon(n):
    P = []
    for _ in range(n):
        line = stdin.readline().strip().split()
        p = Vector(int(line[0]), int(line[1]))
        P.append(p)
    return P

def __main():
    n = int(input())
    P = read_polygon(n)
    P_rev = convex_hull(P)
    while min(P_rev, key=lambda p: (p.y, p.x)) != P_rev[-1]:
        P_rev.appendleft(P_rev.pop())
    print(len(P_rev))
    for i in reversed(P_rev):
        print("{0} {1}".format(i.x, i.y))

if __name__ == '__main__':
    __main()

Submission status: Accepted

Solution code:
from sys import stdin
import operator
readline = stdin.readline


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def ccw(a, b, c):
    b -= a
    c -= a
    if cross(b, c) > 0:  # counter clockwise
        return 1
    elif cross(b, c) < 0:  # clockwise
        return -1
    elif dot(b, c) < 0:  # c--a--b on line
        return -2
    elif abs(b) < abs(c):  # a--b--c on line
        return 2
    return 0


# http://www.prefield.com/algorithm/geometry/convex_hull.html
def convex_hull(ps):
    n = len(ps)
    k = 0
    ps.sort(key=operator.attrgetter('imag'))
    ch = [None] * 2 * n
    # lower-hull
    for i in range(n):
        while k >= 2 and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    # upper-hull
    t = k + 1
    for i in reversed(range(n - 1)):
        while k >= t and ccw(ch[k-2], ch[k-1], ps[i]) <= 0:
            k -= 1
        ch[k] = ps[i]
        k += 1
    return ch[:k - 1]


n = int(readline())
p = [map(int, readline().split()) for _ in range(n)]
p = [x + y * 1j for x, y in p]

p = convex_hull(p)
print(len(p))
for pi in p:
    print(int(pi.real), int(pi.imag))

Submission status: Accepted

Solution code:
from functools import reduce


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def graham_scan(points):
    points.sort(key=lambda p: (p.real, p.imag))
    lh = reduce(keep_left, points, [])
    uh = reduce(keep_left, reversed(points), [])
    lh.extend(uh[1:-1])
    return lh


def keep_left(hull, r):
    if hull:
        prev = hull.pop()
        while hull:
            p = hull[-1]
            if cross(prev - p, r - p) >= 0:
                hull.append(prev)
                break
            prev = hull.pop()
        else:
            hull.append(prev)
    if not hull or hull[-1] != r:
        hull.append(r)
    return hull


n = int(input())
points = [complex(*map(int, input().split())) for _ in range(n)]
result = graham_scan(points)
lr = len(result)
print(lr)
s = min(range(lr), key=lambda i: (result[i].imag, result[i].real))
for p in (result[s:] + result[:s]):
    print(int(p.real), int(p.imag))

Submission status: Accepted

Solution code:
from functools import reduce


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def graham_scan(points):
    points.sort(key=lambda p: (p.imag, p.real))
    lh = reduce(keep_left, points, [])
    uh = reduce(keep_left, reversed(points), [])
    lh.extend(uh[1:-1])
    return lh


def keep_left(hull, r):
    if hull:
        prev = hull.pop()
        while hull:
            p = hull[-1]
            if cross(prev - p, r - p) >= 0:
                hull.append(prev)
                break
            prev = hull.pop()
        else:
            hull.append(prev)
    if not hull or hull[-1] != r:
        hull.append(r)
    return hull


n = int(input())
points = [complex(*map(int, input().split())) for _ in range(n)]
result = graham_scan(points)
print(len(result))
for p in result:
    print(int(p.real), int(p.imag))

Submission status: Accepted

Solution code:

def sgined_area(v0, v1, v2):
    a1 = v1[0] - v0[0]
    a2 = v1[1] - v0[1]
    b1 = v2[0] - v0[0]
    b2 = v2[1] - v0[1]
    return a1*b2 - b1*a2


n = int(input())
vors = [[int(a) for a in input().split() ] for _ in range(n)]
vors.sort(key=lambda v: (v[1], v[0]))

over = [vors[0], vors[1]]

for v in vors[2:]:
    while len(over) > 1 and sgined_area(over[-2], over[-1], v) > 0:
        over.pop()
    over.append(v)
        
under = [vors[0], vors[1]]

for v in vors[2:]:
    while len(under) > 1 and sgined_area(under[-2], under[-1], v) < 0:
        under.pop()
    under.append(v)

print(len(over) + len(under) - 2)
for v in under[:-1]:
    print(v[0], v[1])

for v in reversed(over[1:]):
    print(v[0], v[1])

Submission status: Accepted

Solution code:
n = input()
ps = [map(int, raw_input().split()) for i in xrange(n)]
for i in xrange(n):
    ps[i] = (ps[i][1], ps[i][0])
ps.sort()

def cross(a, b, c):
    return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])
def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs)>1 and cross(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in xrange(n-2, -1, -1):
        p = ps[i]
        while len(qs)>t and cross(qs[-1], qs[-2], p) > 0:
            qs.pop()
        qs.append(p)
    return qs

qs = convex_hull(ps)
print len(qs)-1
for i in xrange(len(qs)-1, 0, -1):
    y, x = qs[i]
    print x, y

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# ????????????????????°???????????°????????????????????\??????????????¢?????´???????????¨??????????§???????
# ?????????http://www.prefield.com/algorithm/geometry/convex_hull.html

import enum


EPS = 1e-10


class PointsRelation(enum.Enum):
    counter_clockwise = 1
    clockwise = 2
    online_back = 3
    on_segment = 4
    online_front = 5


def inner_product(v1, v2):
    return v1.real * v2.real + v1.imag * v2.imag


def outer_product(v1, v2):
    return v1.real * v2.imag - v1.imag * v2.real


def project(a, b):
    return a * inner_product(a, b) / (abs(a) ** 2)


def points_relation(p0, p1, p2):
    v1 = p1 - p0
    v2 = p2 - p0
    op = outer_product(v1, v2)
    if op > EPS:
        return PointsRelation.counter_clockwise
    elif op < -EPS:
        return PointsRelation.clockwise
    elif inner_product(v1, v2) < -EPS:
        return PointsRelation.online_back
    elif abs(v1) < abs(v2):
        return PointsRelation.online_front
    else:
        return PointsRelation.on_segment


def in_place_convex_hull_andrew(ps):
    def judge(p0, p1, p2):
        b = points_relation(p0, p1, p2) != PointsRelation.counter_clockwise
        b &= points_relation(p0, p1, p2) != PointsRelation.online_front
        return b
    if len(ps) < 3:
        return ps
    ps.sort(key=lambda p: p.imag)
    n = len(ps)
    k = 0
    ch = [None for _ in range(2 * n)]
    for i in range(n):
        while k >= 2 and judge(ch[k - 2], ch[k - 1], ps[i]):
            k -= 1
        ch[k] = ps[i]
        k += 1
    t = k + 1
    for i in range(n - 1)[::-1]:
        while k >= t and judge(ch[k - 2], ch[k - 1], ps[i]):
            k -= 1
        ch[k] = ps[i]
        k += 1
    ch = ch[:k - 1]
    return ch


def main():
    n = int(input())
    ps = [complex(*map(int, input().split())) for _ in range(n)]
    ch = in_place_convex_hull_andrew(ps)
    print(len(ch))
    print(*("{:d} {:d}".format(int(p.real), int(p.imag))
            for p in ch), sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
7
2 1
0 0
1 2
2 2
4 2
1 3
3 3

output:
5
0 0
2 1
4 2
3 3
1 3

The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:

sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
"""

import sys
from operator import attrgetter

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def check_ccw(p0, p1, p2):
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        # print('COUNTER_CLOCKWISE')
        flag = 1
    elif cross(a, b) < -1 * EPS:
        # print('CLOCKWISE')
        flag = -1
    elif dot(a, b) < -1 * EPS:
        # print('ONLINE_BACK')
        flag = 2
    elif abs(a) < abs(b):
        # print('ONLINE_FRONT')
        flag = -2
    else:
        # print('ON_SEGMENT')
        flag = 0
    return flag


def convex_check_Andrew(_polygon):
    upper, lower = list(), list()
    _polygon.sort(key=attrgetter('real', 'imag'))

    upper.extend((_polygon[0], _polygon[1]))
    lower.extend((_polygon[-1], _polygon[-2]))

    for i in range(2, points):
        n1 = len(upper)
        while n1 >= 2 and check_ccw(upper[n1 - 2], upper[n1 - 1], _polygon[i]) == 1:
            n1 -= 1
            upper.pop()
        upper.append(_polygon[i])

    for j in range(points - 3, -1, -1):
        n2 = len(lower)
        while n2 >= 2 and check_ccw(lower[n2 - 2], lower[n2 - 1], _polygon[j]) == 1:
            n2 -= 1
            lower.pop()
        lower.append(_polygon[j])

    # print(upper, lower)
    lower.reverse()
    # lower.sort(key=attrgetter('imag', 'real'))
    lower_min = min(lower, key=attrgetter('imag', 'real'))
    # print(lower_min)
    min_index = lower.index(lower_min)
    lower_right = lower[min_index:]
    lower_left = lower[:min_index]
    for k in range(len(upper) - 2, 0, -1):
        lower_right.append(upper[k])
    return lower_right + lower_left


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    points = int(_input[0])
    p_info = map(lambda x: x.split(), _input[1:])

    polygon = [int(x) + int(y) * 1j for x, y in p_info]
    ans = convex_check_Andrew(polygon)
    print(len(ans))
    for ele in ans:
        print(int(ele.real), int(ele.imag))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
7
2 1
0 0
1 2
2 2
4 2
1 3
3 3

output:
5
0 0
2 1
4 2
3 3
1 3

The operator module functions allow multiple levels of sorting. For example, to sort by grade then by age:

sorted(student_tuples, key=itemgetter(1,2))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]

sorted(student_objects, key=attrgetter('grade', 'age'))
[('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
"""

import sys
from operator import attrgetter

EPS = 1e-9


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def check_ccw(p0, p1, p2):
    a, b = p1 - p0, p2 - p0
    if cross(a, b) > EPS:
        # print('COUNTER_CLOCKWISE')
        flag = 1
    elif cross(a, b) < -1 * EPS:
        # print('CLOCKWISE')
        flag = -1
    elif dot(a, b) < -1 * EPS:
        # print('ONLINE_BACK')
        flag = 2
    elif abs(a) < abs(b):
        # print('ONLINE_FRONT')
        flag = -2
    else:
        # print('ON_SEGMENT')
        flag = 0
    return flag


def convex_check_Andrew(_polygon):
    upper, lower = list(), list()
    _polygon.sort(key=attrgetter('real', 'imag'))

    upper.extend((_polygon[0], _polygon[1]))
    lower.extend((_polygon[-1], _polygon[-2]))

    for i in range(2, points):
        n1 = len(upper)
        while n1 >= 2 and check_ccw(upper[n1 - 2], upper[n1 - 1], _polygon[i]) == 1:
            n1 -= 1
            upper.pop()
        upper.append(_polygon[i])

    for j in range(points - 3, -1, -1):
        n2 = len(lower)
        while n2 >= 2 and check_ccw(lower[n2 - 2], lower[n2 - 1], _polygon[j]) == 1:
            n2 -= 1
            lower.pop()
        lower.append(_polygon[j])

    lower.reverse()
    lower_min = min(lower, key=attrgetter('imag', 'real'))
    min_index = lower.index(lower_min)
    lower_right = lower[min_index:]
    lower_left = lower[:min_index]

    for k in range(len(upper) - 2, 0, -1):
        lower_right.append(upper[k])
    return lower_right + lower_left


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    points = int(_input[0])
    p_info = map(lambda x: x.split(), _input[1:])

    polygon = [int(x) + int(y) * 1j for x, y in p_info]
    ans = convex_check_Andrew(polygon)
    print(len(ans))
    for ele in ans:
        print(int(ele.real), int(ele.imag))