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


import sys
from collections import deque
from math import hypot
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[]
for i in range(N):
    x,y=MAP()
    A.append((x, y))


Ay=sorted(A, key=itemgetter(0))
Ay.sort(key=itemgetter(1))


def cross(a, b):
    x1,y1=a
    x2,y2=b
    return x1*y2-y1*x2

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

def calc(a, b, c):
    
    v1=sub(b, a)
    v2=sub(c, a)
    return cross(v1, v2)


def get_dist(v1, v2):
    return hypot(v1[0]-v2[0], v1[1]-v2[1])


def monotone_chain(li):
    
    
    stack=deque()
    stack.append(li[0])
    stack.append(li[1])
    for i in range(2, N):
        
        while len(stack)>=2 and calc(stack[-1], li[i], stack[-2])<0:
            
            stack.pop()
        
        stack.append(li[i])
    res=list(stack)[:-1]

    
    stack=deque()
    stack.append(li[-1])
    stack.append(li[-2])
    for i in range(N-3, -1, -1):
        while len(stack)>=2 and calc(stack[-1], li[i], stack[-2])<0:
            stack.pop()
        stack.append(li[i])
    res+=list(stack)[:-1]

    return res

ans=monotone_chain(Ay)
print(len(ans))
[print(x, y) for x, y in ans]

Solution (Python):
import cmath
EPS = 1e-10


def OuterProduct(one, two):
	tmp = one.conjugate() * two
	return tmp.imag



def CCW(p, q, r):
	one, two = q-p, r-q
	if OuterProduct(one, two) > -EPS:
		return True
	else:
		return False


def ConvexHull(dots):
	dots.sort(key=lambda x: (x.imag, x.real))
	res1 = [dots[0]]
	for d in dots[1:]:
		if len(res1) == 1:
			res1.append(d)
		else:
			while len(res1) > 1 and not CCW(res1[-2], res1[-1], d):
				res1.pop()
			res1.append(d)
	dots.reverse()
	res2 = [dots[0]]
	for d in dots[1:]:
		if len(res2) == 1:
			res2.append(d)
		else:
			while len(res2) > 1 and not CCW(res2[-2], res2[-1], d):
				res2.pop()
			res2.append(d)
	return res1[:-1] + res2[:-1]

n = int(input())
dots = []
for _ in range(n):
	x, y = map(int, input().split())
	dots.append(complex(x, y))

ch = ConvexHull(dots)
print(len(ch))
for v in ch:
	print(round(v.real), round(v.imag))

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-9
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def sgn(a):
    if a < -eps: return -1
    if a >  eps: return  1
    return 0

class Point:
    def __init__(self,x,y):
        self.x = x
        self.y = y
        pass

    def tolist(self):
        return [self.x,self.y]

    def __add__(self,p):
        return Point(self.x+p.x, self.y+p.y)
    def __iadd__(self,p):
        return self + p

    def __sub__(self,p):
        return Point(self.x - p.x, self.y - p.y)
    def __isub__(self,p):
        return self - p

    def __truediv__(self,n):
        return Point(self.x/n, self.y/n)
    def __itruediv__(self,n):
        return self / n

    def __mul__(self,n):
        return Point(self.x*n, self.y*n)
    def __imul__(self,n):
        return self * n

    def __lt__(self,other):
        tmp = sgn(self.y - other.y)
        if tmp != 0:
            return tmp < 0
        else:
            return sgn(self.x - other.x) < 0


    def abs(self):
        return math.sqrt(self.x**2+self.y**2)

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

    def det(self,p):
        return self.x * p.y - self.y*p.x

    def arg(self,p):
        return math.atan2(y,x)


def iSP(a,b,c):
    tmp = sgn((b-a).det(c-a))
    if tmp > 0:   return 1   
    elif tmp < 0: return -1  
    else: 
        if sgn((b-a).dot(c-a)) < 0: return -2 
        if sgn((a-b).dot(c-b)) < 0: return  2 
        return 0 


def isToleranceLine(a,b,c,d):
    if sgn((b-a).det(c-d)) != 0: return 1 
    else:
        if sgn((b-a).det(c-a)) != 0: return 0 
        else: return -1 


def isToleranceSegline(a,b,c,d):
    return sgn(iSP(a,b,c)*iSP(a,b,d))<=0 and sgn(iSP(c,d,a)*iSP(c,d,b)) <= 0


def Intersection(a,b,c,d):
    tmp1 = ((b-a)*(c-a)).det(d-c)
    tmp2 = (b-a).det(d-c)
    return a+(tmp1/tmp2)


def DistanceLineToPoint(a,b,c):
    return abs(((c-a).det(b-a))/((b-a).abs()))


def DistanceSeglineToPoint(a,b,c):
    if sgn((b-a).dot(c-a)) < 0: 
        return (c-a).abs()
    if sgn((a-b).dot(c-b)) < 0: 
        return (c-b).abs()
    return DistanceLineToPoint(a,b,c)


def PolygonArea(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
    return S


def PolygonG(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    G = Point(0,0)
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
        G += (Plist[i-1]+Plist[i])/3*tmpS
    return G/S


def ConvexHull(Plist):
    Plist.sort()
    L = len(Plist)
    qu = deque([])
    quL = 0
    for p in Plist:
        while quL >= 2 and iSP(qu[quL-2],qu[quL-1],p) == 1:
            qu.pop()
            quL -= 1
        qu.append(p)
        quL += 1

    qd = deque([])
    qdL = 0
    for p in Plist:
        while qdL >= 2 and iSP(qd[qdL-2],qd[qdL-1],p) == -1:
            qd.pop()
            qdL -= 1
        qd.append(p)
        qdL += 1

    qd.pop()
    qu.popleft()
    hidari = list(qd) + list(reversed(qu)) 
    return hidari

N = int(input())
PP = [Point(*inpl()) for _ in range(N)]
PP = ConvexHull(PP)
print(len(PP))
for p in PP:
    print(*p.tolist())

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

source = (0,0)
def area(a, b, source):
    return (a[0]-source[0])*(b[1]-source[1]) - (b[0]-source[0])*(a[1]-source[1])

def div_con(coordinate):
    s = sorted(set(coordinate), key=lambda x: (x[1], x[0]))
    seq = []
    for i in range(len(s)):
        while len(seq) > 1 and area(seq[-2], s[i], seq[-1]) > 0:
            seq.pop()
        seq.append(s[i])
    t = len(seq)
    for i in range(len(s) - 2, -1, -1):
        while len(seq) > t and area(seq[-2], s[i], seq[-1]) > 0:
            seq.pop()
        seq.append(s[i])
        
    result = seq[:-1]
    return result


num = int(input())

coordinate = []

for i in range(num):
  coordinate.append(tuple(map(int, input().split())))
result = div_con(coordinate)

print(len(result))
for item in result:
  print(item[0],item[1])

Solution (Python):
def cro(a,b):
    return a.real * b.imag - a.imag * b.real

"""class Point:
    def __init__(self,x,y):
        self.x=x
        self.y=y
    def __repr__(self):
        return repr((self.x, self.y))
"""

n = int(input())
p = []
po = []
for i in range(n):
    x,y=list(int(x) for x in input().split()) 
    p.append(complex(x,y))

po=sorted(p, key=lambda x:(x.imag, x.real))
ps,j = [0]*(n+1),0


for i in range(n):
    while j > 1 and cro(ps[j-1]-ps[j-2],po[i]-ps[j-1]) < 0:
        j-=1
    ps[j] = po[i]
    j+=1

l = j

for i in reversed(range(n-1)):    
    while j > l and cro(ps[j-1]-ps[j-2],po[i]-ps[j-1]) < 0:
        j-=1
    ps[j] = po[i]
    j+=1
 
k = ps[0:j-1]

print(len(k))

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

Solution (Python):
import math

convex_hull_list = []

def isRight_from_gaiseki(p,q,r):
    area = (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])
    return area

if __name__ == '__main__':
    N_vertex = int(input())

    point_pairs = [(0,0)]*N_vertex

    
    convex_hull = [(10001,10001)]*(2*N_vertex)

    
    for i in range(N_vertex):
        x,y = map(int, input().split())
        point_pairs[i] = (x,y)
    point_pairs = sorted(point_pairs, key=lambda x:(x[1],x[0]))
    if(N_vertex == 3):
        print(N_vertex)
        if(isRight_from_gaiseki(point_pairs[0],point_pairs[1],point_pairs[2]) == 0):
            point_pairs = sorted(point_pairs, key=lambda x:(x[0],x[1]))
            print("{0} {1}".format(point_pairs[0][0],point_pairs[0][1]))
            print("{0} {1}".format(point_pairs[1][0],point_pairs[1][1]))
            print("{0} {1}".format(point_pairs[2][0],point_pairs[2][1]))
        else:
            print("{0} {1}".format(point_pairs[0][0],point_pairs[0][1]))
            print("{0} {1}".format(point_pairs[1][0],point_pairs[1][1]))
            print("{0} {1}".format(point_pairs[2][0],point_pairs[2][1]))
    else:
        k = 0

        
        for i in range(0,N_vertex):
            while(k >= 2 and isRight_from_gaiseki(convex_hull[k-2],convex_hull[k-1],point_pairs[i])<0):
                k = k - 1
            convex_hull[k] = point_pairs[i]
            k = k + 1

        t = k + 1
        
        for i in range(N_vertex-1, 0, -1):
            
            while(k >= t and isRight_from_gaiseki(convex_hull[k-2],convex_hull[k-1],point_pairs[i-1])<0):
                k = k - 1
            
            convex_hull[k] = point_pairs[i-1]
            k = k + 1
        convex_hull_valid_num = k - 1
        print(convex_hull_valid_num)
        
        for i in range(0,convex_hull_valid_num):
            print("{0} {1}".format(convex_hull[i][0],convex_hull[i][1]))

Solution (Python):


def determinants(p1, p2, origin=(0, 0)):
    return (p1[0]-origin[0])*(p2[1]-origin[1]) - (p2[0]-origin[0])*(p1[1]-origin[1])


def convex_hull(p):
    h = []
    s = sorted(set(p), key=lambda x: (x[1], x[0]))
    for i in range(len(s)):
        while len(h) > 1 and determinants(h[-2], s[i], h[-1]) > 0:
            h.pop()
        h.append(s[i])
    l = len(h)
    for i in range(len(s) - 2, -1, -1):
        while len(h) > l and determinants(h[-2], s[i], h[-1]) > 0:
            h.pop()
        h.append(s[i])
    return h[:-1]


n = int(input())
p = [tuple(map(int, input().split())) for _ in range(n)]
result = convex_hull(p)
print(len(result))
for r in result:
    print("{} {}".format(r[0], r[1]))

Solution (Python):
import math

EPS = 1e-10


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

    def __add__(self, v):
        return Vector2(self.x+v.x, self.y+v.y)

    def __sub__(self, v):
        return Vector2(self.x-v.x, self.y-v.y)

    def __mul__(self, v):
        return Vector2(self.x*v, self.y*v)

    def __truediv__(self, v):
        return Vector2(self.x/v, self.y/v)

    def __abs__(self):
        return math.sqrt(float(self.x*self.x+self.y*self.y))

    def __str__(self):
        return f"({self.x},{self.y})"

    def __lt__(self, v):
        if math.isclose(self.x, v.x):
            return self.y < v.y
        return self.x < v.x

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

    def cross(self, v):
        return self.x*v.y-self.y*v.x

    def norm(self):
        d = abs(self)
        return Vector2(self.x/d, self.y/d)


def projection(v1, v2, p):
    v12 = (v2-v1).norm()
    v1p = p-v1
    d = v12.dot(v1p)
    return v1+v12*d


def distanceLP(v1, v2, p):
    '''
    v1 -> v2の直線とpとの距離
    '''
    return abs((v2-v1).cross(p-v1))/abs(v2-v1)


def distanceSP(v1, v2, p):
    '''
    v1 -> v2の線分とpとの距離
    '''
    if (v2-v1).dot(p-v1) < 0.0:
        return abs(p-v1)
    if (v1-v2).dot(p-v2) < 0.0:
        return abs(p-v2)
    return distanceLP(v1, v2, p)


def ccw(p0, p1, p2):
    c = (p1-p0).cross(p2-p0)
    if math.isclose(c, 0.0, abs_tol=EPS):
        d = (p1-p0).dot(p2-p0)
        if d < 0.0:
            return 2
        else:
            d1 = abs(p1-p0)
            d2 = abs(p2-p0)
            if d1 < d2:
                return -2
            else:
                return 0
    elif c < 0.0:
        return -1
    else:
        return 1


def intersect(p1, p2, p3, p4):
    '''
    p1p2とp3p4の交差判定
    '''
    
    
    
    
    
    c1 = ccw(p1, p2, p3)*ccw(p1, p2, p4)
    c2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)
    return c1 <= 0.0 and c2 <= 0.0


def distance(a1, a2, b1, b2):
    '''
    線分a1a2とb1b2の距離
    '''
    if intersect(a1, a2, b1, b2):
        return 0.0
    return min([
        min([distanceSP(a1, a2, b1), distanceSP(a1, a2, b2)]),
        min([distanceSP(b1, b2, a1), distanceSP(b1, b2, a2)])
    ])


n = int(input())
p = [list(map(int, input().split())) for _ in range(n)]

'''
凸包を求める
アンドリューのアルゴリズム
'''
u, l = [], []
p.sort()


u.append(p[0])
u.append(p[1])
for i in range(2, n):
    pv = Vector2(p[i][0], p[i][1])
    while len(u) > 1:
        p1 = Vector2(u[-1][0], u[-1][1])
        p2 = Vector2(u[-2][0], u[-2][1])
        if ccw(p2, p1, pv) == 1.0:
            u.pop(-1)
        else:
            break
    u.append(p[i])


l.append(p[-1])
l.append(p[-2])
for i in range(n-3, -1, -1):
    pv = Vector2(p[i][0], p[i][1])
    while len(l) > 1:
        p1 = Vector2(l[-1][0], l[-1][1])
        p2 = Vector2(l[-2][0], l[-2][1])
        if ccw(p2, p1, pv) == 1.0:
            l.pop(-1)
        else:
            break
    l.append(p[i])
l.reverse()

ans = l+list(reversed(u[1:-1]))
print(len(ans))

si = 0
for i, v in enumerate(ans):
    if v[1] < ans[si][1]:
        si = i

for i in range(len(ans)):
    print(f"{ans[(i+si)%len(ans)][0]} {ans[(i+si)%len(ans)][1]}")

Solution (Python):



from operator import itemgetter


def cross(v1, v2):
    x1, y1 = v1
    x2, y2 = v2
    return x1 * y2 - x2 * y1


def convex_hull(ps):
    ps.sort(key=itemgetter(0))
    ps.sort(key=itemgetter(1))
    p0 = ps[0]
    vs = [(p0, p0)]
    for p in ps[1:]:
        x, y = p
        p1, v1 = vs.pop()
        x1, y1 = p1
        v = (x-x1, y-y1)
        while vs and cross(v1, v) < 0:
            p1, v1 = vs.pop()
            x1, y1 = p1
            v = (x-x1, y-y1)

        vs.append((p1, v1))
        vs.append((p, v))

    for p in reversed(ps[:-1]):
        x, y = p
        p1, v1 = vs.pop()
        x1, y1 = p1
        v = (x-x1, y-y1)
        while vs and cross(v1, v) < 0:
            p1, v1 = vs.pop()
            x1, y1 = p1
            v = (x-x1, y-y1)

        vs.append((p1, v1))
        vs.append((p, v))

    return [p for p, v in vs[:-1]]


def run():
    n = int(input())
    ps = []

    for _ in range(n):
        x, y = [int(i) for i in input().split()]
        ps.append((x, y))

    convex = convex_hull(ps)

    print(len(convex))
    for p in convex:
        print('{} {}'.format(*p))


if __name__ == '__main__':
    run()

Solution (Python):
import math
from typing import Union, Tuple, List

class Point(object):
    __slots__ = ['x', 'y']

    def __init__(self, x, y):
        self.x = x
        self.y = y

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

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

    def __mul__(self, other: Union[int, float]):
        return Point(self.x * other, self.y * other)

    def norm(self):
        return pow(self.x, 2) + pow(self.y, 2)

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

    def __repr__(self):
        return f"({self.x},{self.y})"


class Vector(Point):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt2.x - pt1.x, pt2.y - pt1.y)
        self.pt1 = pt1
        self.pt2 = pt2

    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 arg(self) -> float:
        return math.atan2(self.y, self.x)

    @staticmethod
    def polar(r, theta) -> Point:
        return Point(r * math.cos(theta), r * math.sin(theta))

    def __repr__(self):
        return f"({self.x},{self.y})"


class Segment(Vector):
    __slots__ = ['x', 'y', 'pt1', 'pt2']

    def __init__(self, pt1: Point, pt2: Point):
        super().__init__(pt1, pt2)

    def projection(self, pt: Point)-> Point:
        t = self.dot(Vector(self.pt1, pt)) / self.norm()
        return self.pt1 + self * t

    def reflection(self, pt: Point) -> Point:
        return self.projection(pt) * 2 - pt

    def is_intersected_with(self, other) -> bool:
        if (self.point_geometry(other.pt1) * self.point_geometry(other.pt2)) <= 0\
                and other.point_geometry(self.pt1) * other.point_geometry(self.pt2) <= 0:
            return True
        else:
            return False

    def point_geometry(self, pt: Point) -> int:
        """
        [-2:"Online Back", -1:"Counter Clockwise", 0:"On Segment", 1:"Clockwise",  2:"Online Front"]
        """
        vec_pt1_to_pt = Vector(self.pt1, pt)
        cross = self.cross(vec_pt1_to_pt)
        if cross > 0:
            return -1   
        elif cross < 0:
            return 1    
        else:           
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    
            else:       
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    
                else:
                    return 0    

    def cross_point(self, other) -> Point:
        d1 = abs(self.cross(Vector(self.pt1, other.pt1)))       
        d2 = abs(self.cross(Vector(self.pt1, other.pt2)))       
        t = d1 / (d1 + d2)
        return other.pt1 + other * t

    def distance_to_point(self, pt: Point) -> Union[int, float]:
        vec_pt1_to_pt = Vector(self.pt1, pt)
        if self.dot(vec_pt1_to_pt) <= 0:
            return vec_pt1_to_pt.abs()
        vec_pt2_to_pt = Vector(self.pt2, pt)
        if Vector.dot(self * -1, vec_pt2_to_pt) <= 0:
            return vec_pt2_to_pt.abs()
        return (self.projection(pt) - pt).abs()

    def distance_to_segment(self, other) -> Union[int, float]:
        if self.is_intersected_with(other):
            return 0.0
        else:
            return min(
                self.distance_to_point(other.pt1),
                self.distance_to_point(other.pt2),
                other.distance_to_point(self.pt1),
                other.distance_to_point(self.pt2)
            )

    def __repr__(self):
        return f"{self.pt1},{self.pt2}"


class Circle(Point):
    __slots__ = ['x', 'y', 'r']
    def __init__(self, x, y, r):
        super().__init__(x, y)
        self.r = r

    def cross_point_with_circle(self, other) -> Tuple[Point, Point]:
        vec_self_to_other = Vector(self, other)
        vec_abs = vec_self_to_other.abs()
        
        
        t = ((pow(self.r, 2) - pow(other.r, 2)) / pow(vec_abs, 2) + 1) / 2
        pt = (other - self) * t
        abs_from_pt = math.sqrt(pow(self.r, 2) - pt.norm())
        inv = Point(vec_self_to_other.y / vec_abs,  - vec_self_to_other.x / vec_abs) * abs_from_pt
        pt_ = self + pt
        return (pt_ + inv), (pt_ - inv)

    def cross_point_with_circle2(self, other) -> Tuple[Point, Point]:
        vec_self_to_other = Vector(self, other)
        vec_abs = vec_self_to_other.abs()
        
        

        theta_base_to_other = vec_self_to_other.arg()
        theta_other_to_pt = math.acos((pow(self.r, 2) + pow(vec_abs, 2) - pow(other.r, 2)) / (2 * self.r * vec_abs))

        return self + Vector.polar(self.r, theta_base_to_other + theta_other_to_pt),\
               self + Vector.polar(self.r, theta_base_to_other - theta_other_to_pt)

    def __repr__(self):
        return f"({self.x},{self.y}), {self.r}"


class Polygon(object):
    __slots__ = ['vertices', 'num_vertices']

    def __init__(self, vertices):
        self.vertices = vertices
        self.num_vertices = len(vertices)

    def contains_point(self, pt: Point) -> int:
        """
        The coordinates of points must be given in the order of visit of them.
        {0:"not contained", 1: "on a edge", 2:"contained"}
        """
        cross_count = 0
        for i in range(self.num_vertices):
            vec_a = Vector(pt, self.vertices[i])
            vec_b = Vector(pt, self.vertices[(i+1) % self.num_vertices])
            if vec_a.y > vec_b.y:
                vec_a, vec_b = vec_b, vec_a
            dot   = vec_a.dot(  vec_b)
            cross = vec_a.cross(vec_b)

            
            if math.isclose(cross, 0.0) and dot <= 0:
                return 1        
            elif vec_a.y <= 0.0 < vec_b.y and cross > 0:
                cross_count += 1
        return [0, 2][cross_count % 2]

    @staticmethod
    def can_form_convex(pt_a: Point, pt_mid: Point, pt_b: Point) -> bool:
        vec_a = Vector(pt_mid, pt_a)
        vec_b = Vector(pt_mid, pt_b)

        if vec_a.cross(vec_b) >= 0:
            return True
        else:
            return False

    @staticmethod
    def append_convex_vertex(vertices, convex_full):
        not_used_vertices = []
        for vtx in vertices:
            if len(convex_full) >= 2:
                for j in range(1, len(convex_full))[::-1]:
                    if Polygon.can_form_convex(convex_full[j-1], convex_full[j], vtx):
                        break
                    not_used_vertices.append(convex_full.pop())
            convex_full.append(vtx)
        return not_used_vertices

    @staticmethod
    def convex_full(vertices: List[Point]) -> List[Point]:
        
        vertices.sort(key=lambda pt: (pt.x, pt.y))
        convex_full = []
        
        not_used_vertices = Polygon.append_convex_vertex(vertices, convex_full)

        
        not_used_vertices.sort(key=lambda pt: (pt.x, pt.y), reverse=True)
        not_used_vertices.append(vertices[0])
        
        _ = Polygon.append_convex_vertex(not_used_vertices, convex_full)

        return convex_full[:-1]

    def __repr__(self):
        return f"{self.vertices}"


def main():
    num_vertices = int(input())
    vertices = []
    for i in range(num_vertices):
        pt_x, pt_y = map(int, input().split())
        vertices.append(Point(pt_x, pt_y))

    convex_full = Polygon.convex_full(vertices)

    start_vtx = sorted(convex_full, key=lambda pt: (pt.y, pt.x))[0]
    id = convex_full.index(start_vtx)
    n = len(convex_full)

    print(n)
    for i in range(n):
        pt = convex_full[(id-i) % n]
        print(f'{pt.x} {pt.y}')


main()

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, j = [0] * (n+1), 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):
def ccw(p1, p2, p3):
    return (p2[1] - p1[1]) * (p3[0] - p1[0]) - (p2[0] - p1[0]) * (p3[1] - p1[1]) > 0



def andrew(point_list):
    u = []
    l = []
    point_list.sort()

    u.append(point_list[0])
    u.append(point_list[1])
    
    l.append(point_list[-1])
    l.append(point_list[-2])

    
    for p in point_list[2:]:
        while ccw(u[-1], u[-2], p):
            u.pop()
            if len(u) == 1:
                break
        u.append(p)

    
    for p in point_list[-3::-1]:
        while ccw(l[-1], l[-2], p):
            l.pop()
            if len(l) == 1:
                break
        l.append(p)

    
    u.pop()
    l.pop()
    convex_hull = u + l

    
    print(len(convex_hull))
    for p in convex_hull:
        y, x = p
        print(x, y)

import sys

file_input = sys.stdin

n = int(file_input.readline())

P = []
for l in file_input:
    x, y = map(int, l.split())
    P.append((y, x))


andrew(P)

Solution (Python):
import math

EPS = 1e-10

def equals(a, b):
    return abs(a - b) < EPS


class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, p):
        return Point(self.x + p.x, self.y + p.y)

    def __sub__(self, p):
        return Point(self.x - p.x, self.y - p.y)

    def __mul__(self, a):
        return Point(self.x * a, self.y * a)

    def __rmul__(self, a):
        return self * a

    def __truediv__(self, a):
        return Point(self.x / a, self.y / a)

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

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

    def __lt__(self, p):
        if self.x != p.x:
            return self. x < p.x
        else:
            return self.y < p.y

    def __eq__(self, p):
        return equals(self.x, p.x) and equals(self.y, p.y)


def dot(a, b):
    return a.x * b.x + a.y * b.y


def cross(a, b):
    return a.x * b.y - a.y * b.x


COUNTER_CLOCKWISE = 1
CLOCKWISE = -1
ONLINE_BACK = 2
ONLINE_FRONT = -2
ON_SEGMENT = 0


def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if cross(a, b) > EPS:
        return COUNTER_CLOCKWISE
    if cross(a, b) < -EPS:
        return CLOCKWISE
    if dot(a, b) < -EPS:
        return ONLINE_BACK
    if a.norm() < b.norm():
        return ONLINE_FRONT
    return ON_SEGMENT


def andrewScan(s):
    n = len(s)
    if n < 3:
        return s
    u = []
    l = []
    s.sort()
    u.append(s[0])
    u.append(s[1])
    l.append(s[-1])
    l.append(s[-2])

    for i in range(2, n):
        for m in range(len(u), 1, -1):
            if ccw(u[m-2], u[m-1], s[i]) != COUNTER_CLOCKWISE:
                break
            u.pop()
        u.append(s[i])

    for i in range(n-3, -1, -1):
        for m in range(len(l), 1, -1):
            if ccw(l[m-2], l[m-1], s[i]) != COUNTER_CLOCKWISE:
                break
            l.pop()
        l.append(s[i])

    l.reverse()
    l.extend(u[-2:0:-1])
    return l


if __name__ == '__main__':
    n = int(input())
    g = []
    for i in range(n):
        x, y =  [int(v) for v in input().split()]
        g.append(Point(x, y))

    ans = andrewScan(g)

    minv = ans[0]
    mini = 0
    for i in range(1, len(ans)):
        if ans[i].y < minv.y or (ans[i].y == minv.y and ans[i].x < minv.x):
            minv = ans[i]
            mini = i
    ans = ans[mini:] + ans[:mini]

    print(len(ans))
    for v in ans:
        print('{0} {1}'.format(v.x, v.y))