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  x 1  y 1  x 2  y 2 : x n  y n  The first integer n is the number of points in P . The coordinate of the i -th point p i is given by two integers x i and y i . 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 ≤ x i , y i ≤ 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

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

    
    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

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

Solution (Python):
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:  
        return 1
    elif cross(b, c) < 0:  
        return -1
    elif dot(b, c) < 0:  
        return -2
    elif abs(b) < abs(c):  
        return 2
    return 0



def convex_hull(ps):
    n = len(ps)
    k = 0
    ps.sort(key=operator.attrgetter('imag'))
    ch = [None] * 2 * n
    
    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
    
    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))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):

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

Solution (Python):
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

Solution (Python):




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

Solution (Python):



"""
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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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))

Solution (Python):



"""
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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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))

Solution (Python):



"""
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
"""

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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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))

Solution (Python):



"""
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
"""

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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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]

    return lower_right + upper[-2:0:-1] + 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))

Solution (Python):



"""
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
"""

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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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]

    return lower_right + upper[-2:0:-1] + 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))

Solution (Python):



"""
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
"""

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:
        
        flag = 1
    elif cross(a, b) < -1 * EPS:
        
        flag = -1
    elif dot(a, b) < -1 * EPS:
        
        flag = 2
    elif abs(a) < abs(b):
        
        flag = -2
    else:
        
        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'))
    init_index = lower.index(lower_min)
    
    return lower[init_index:] + upper[-2:0:-1] + lower[:init_index]


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

Solution (Python):
def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def ccw(p0, p1, p2):
    if cross(p1 - p0, p2 - p0) > 0:
        return True
    else:
        False


import collections

def andrew(point_list):
    point_list.sort(key = lambda c: (c.imag, c.real))
    point_que = collections.deque(point_list)
    convex_hull = []
    rest_points = []
    start_point = point_que.popleft()

    
    convex_hull.append(start_point)
    convex_hull.append(point_que.popleft())

    while point_que:
        new_point = point_que.popleft()
        while ccw(convex_hull[-1], convex_hull[-2], new_point):
            rest_points.append(convex_hull.pop())
            if len(convex_hull) == 1:
                break
        convex_hull.append(new_point)

    
    rest_points.append(start_point)
    rest_points.sort(key = lambda c: c.imag)

    while rest_points:
        new_point = rest_points.pop()
        while ccw(convex_hull[-1], convex_hull[-2], new_point):
            convex_hull.pop()
        convex_hull.append(new_point)

    
    convex_hull.pop()
    print(len(convex_hull))
    for p in convex_hull:
        print("{0:.0f} {1:.0f}".format(p.real, p.imag))


def string_to_complex(s):
    x, y = map(int, s.split())
    return x + y * 1j

import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [string_to_complex(file_input.readline()) for i in range(n)]


andrew(P)

Solution (Python):
def cross(c1, c2):
    return c1.real * c2.imag - c1.imag * c2.real

def ccw(p0, p1, p2):
    if cross(p1 - p0, p2 - p0) > 0:
        return True
    else:
        False


import collections

def andrew(point_list):
    point_list.sort(key = lambda c: (c.imag, c.real))
    point_que = collections.deque(point_list)
    convex_hull = []
    rest_points = []
    start_point = point_que.popleft()

    
    convex_hull.append(start_point)
    convex_hull.append(point_que.popleft())

    while point_que:
        new_point = point_que.popleft()
        while ccw(convex_hull[-1], convex_hull[-2], new_point):
            rest_points.append(convex_hull.pop())
            if len(convex_hull) == 1:
                break
        convex_hull.append(new_point)

    
    rest_points.append(start_point)
    rest_points.sort(key = lambda c: c.imag)

    while rest_points:
        new_point = rest_points.pop()
        while ccw(convex_hull[-1], convex_hull[-2], new_point):
            convex_hull.pop()
        convex_hull.append(new_point)

    
    convex_hull.pop()
    print(len(convex_hull))
    print('\n'.join(map(lambda p: "{0:.0f} {1:.0f}".format(p.real, p.imag), convex_hull)))


def string_to_complex(s):
    x, y = map(int, s.split())
    return x + y * 1j

import sys

file_input = sys.stdin

n = int(file_input.readline())

P = [string_to_complex(file_input.readline()) for i in range(n)]


andrew(P)

Solution (Python):
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)

Solution (Python):
import sys
from operator import itemgetter, attrgetter
from itertools import starmap
import cmath
from math import isinf, sqrt, acos, atan2
readline = sys.stdin.readline
EPS = 1e-9
ONLINE_FRONT = -2
CLOCKWISE = -1
ON_SEGMENT = 0
COUNTER_CLOCKWISE = 1
ONLINE_BACK = 2
class Circle(object):
    __slots__ = ('c', 'r')
    def __init__(self, c, r):
        self.c = c
        self.r = r
class Segment(object):
    __slots__ = ('fi', 'se')
    def __init__(self, fi, se):
        self.fi = fi
        self.se = se
Line = Segment
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 norm(base):
    return abs(base) ** 2
def project(s, p2):
    base = s.fi - s.se
    r = dot(p2 - s.fi, base) / norm(base)
    return s.fi + base * r
def reflect(s, p):
    return p + (project(s, p) - p) * 2.0
def ccw(p1, p2, p3):
    a = p2 - p1
    b = p3 - p1
    if cross(a, b) > EPS: return 1
    if cross(a, b) < -EPS: return -1
    if dot(a, b) < -EPS: return 2
    if norm(a) < norm(b): return -2
    return 0
def intersect4(p1, p2, p3, p4):
    return (ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 and
			ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0)
def intersect2(s1, s2):
    return intersect4(s1.fi, s1.se, s2.fi, s2.se)
def getDistance(a, b):  return abs(a - b)
def getDistanceLP(l, p):
    return abs(cross(l.se - l.fi, p - l.fi) / abs(l.se - l.fi))
def getDistanceSP(s, p):
    if dot(s.se - s.fi, p - s.fi) < 0.0: return abs(p - s.fi)
    if dot(s.fi - s.se, p - s.se) < 0.0: return abs(p - s.se)
    return getDistanceLP(s, p)
def getDistances(s1, s2):
    if intersect2(s1, s2): return 0.0
    return min(getDistanceSP(s1, s2.fi), getDistanceSP(s1, s2.se),
               getDistanceSP(s2, s1.fi), getDistanceSP(s2, s1.se))
def getCrossPoint(s1, s2):
	base = s2.se - s2.fi
	d1 = abs(cross(base, s1.fi - s2.fi))
	d2 = abs(cross(base, s1.se - s2.fi))
	t = d1 / (d1 + d2)
	return s1.fi + (s1.se - s1.fi) * t
def getCrossPointsCL(c, l):
    pr = project(l, c.c)
    e = (l.se - l.fi) / abs(l.se - l.fi)
    base = sqrt(c.r * c.r - norm(pr - c.c))
    return Segment(*sorted((pr + e * base, pr - e * base)), key=attrgetter('real', 'imag'))
def getCrossPointsCC(c1, c2):
    d = abs(c1.c - c2.c)
    a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2.0 * c1.r * d))
    t = cmath.phase(c2.c - c1.c)
    return Segment(*sorted((c1.c + cmath.rect(c1.r, t + a), c1.c + cmath.rect(c1.r, t - a)), key=attrgetter('real', 'imag')))
def contains(g, p):
    n = len(g)
    x = False
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if abs(cross(a, b)) < EPS and dot(a, b) < EPS: return 1
        if a.imag > b.imag: a, b = b, a
        if a.imag < EPS and EPS < b.imag and cross(a, b) > EPS: x = not x
    return 2 if x else 0
def andrewScan(s):
    if len(s) < 3: return s
    u = []
    l = []
    s.sort(key=attrgetter('imag'))
    u.append(s[0])
    u.append(s[1])
    l.append(s[-1])
    l.append(s[-2])
    _ccw = 0
    for i in range(2, len(s)):
        for q in range(len(u), 1, -1):
            _ccw = ccw(u[q - 2], u[q - 1], s[i])
            if not (_ccw != CLOCKWISE and _ccw != ONLINE_FRONT): break
            u.pop()
        u.append(s[i])
    for i in range(len(s) - 3, -1, -1):
        for q in range(len(l), 1, -1):
            _ccw = ccw(l[q - 2], l[q - 1], s[i])
            if not (_ccw != CLOCKWISE and _ccw != ONLINE_FRONT): break
            l.pop()
        l.append(s[i])
    l.reverse()
    for i in range(len(u) - 2, 0, -1):
        l.append(u[i])
    return l
n = int(readline())
pg = [complex(*map(int, readline().split())) for _ in [0] * n]
ans = andrewScan(pg)
print(len(ans))
for i in range(len(ans)):
    print(int(ans[i].real), int(ans[i].imag))