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

Solution code:
# -*- coding: utf-8 -*-

import collections
import math


class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

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

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

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

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

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

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

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

    def abs2(self):
        return float(self.x * self.x + self.y * self.y)

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

    def cross(self, other):  # cross product
        return self.x * other.y - self.y * other.x


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > 0:
        return 1  # COUNTER_CLOCKWISE
    elif a.cross(b) < 0:
        return -1  # CLOCKWISE
    elif a.dot(b) < 0:
        return 2  # ONLINE_BACK
    elif abs(a) < abs(b):
        return -2  # ONLINE_FRONT
    else:
        return 0  # ON_SEGMENT


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


def project(l, p):
    p1, p2 = l
    base = p2 - p1
    hypo = p - p1
    return p1 + base * (hypo.dot(base) / abs(base)**2)


class Circle():
    def __init__(self, c, r):
        self.c = c
        self.r = r


def getCrossPoints(c, l):
    pr = project(l, c.c)
    p1, p2 = l
    e = (p2 - p1) / abs(p2 - p1)
    base = math.sqrt(c.r * c.r - (pr - c.c).abs2())
    return [pr + e * base, pr - e * base]


def polar(r, a):
    return Vector2(r * math.cos(a), r * math.sin(a))


def getCrossPointsCircle(c1, c2):
    base = c2.c - c1.c
    d = abs(base)
    a = math.acos((c1.r**2 + d**2 - c2.r**2) / (2 * c1.r * d))
    t = math.atan2(base.y, base.x)
    return [c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)]


def contains(g, p):
    n = len(g)
    x = 0
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if a.cross(b) == 0 and a.dot(b) <= 0:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y <= 0 and b.y > 0 and a.cross(b) > 0:
            x += 1

    if x % 2 == 1:
        return 2
    else:
        return 0

def andrewScan(s):
    u = []
    l = []
    s = sorted(s, key=lambda x: (x.x, x.y))
    if len(s) < 3:
        return s
    u.append(s[0])
    u.append(s[1])
    l.append(s[-1])
    l.append(s[-2])

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

    for i in range(len(s)-3, -1, -1):
        for n in range(len(l), 1, -1):
            if ccw(l[n-2], l[n-1], s[i]) != 1:
                break
            else:
                l.pop()
        l.append(s[i])
    
    ans = l+u[1:-1]
    ans.reverse()
    return ans


if __name__ == '__main__':

    n = int(input())
    s = []
    for _ in range(n):
        a, b = map(int, input().split())
        s.append(Vector2(a, b))
    ans = andrewScan(s)
    index = ans.index((min(ans, key=lambda x:x.y)))
    print(len(ans))
    for i in range(len(ans)):
        p = ans[(index +i)%len(ans)]
        print(p.x, p.y)

Submission status: Accepted

Solution code:
def det(p1, p2, org=(0, 0)):
    """cross product"""
    return (p1[0]-org[0])*(p2[1]-org[1]) - (p2[0]-org[0])*(p1[1]-org[1])

def convex_hull(points):
    s = sorted(set(points), key=lambda x: (x[1], x[0]))
    hull = []
    for i in range(len(s)):
        while len(hull) > 1 and det(hull[-2], s[i], hull[-1]) > 0:
            hull.pop()
        hull.append(s[i])
    t = len(hull)
    for i in range(len(s) - 2, -1, -1):
        while len(hull) > t and det(hull[-2], s[i], hull[-1]) > 0:
            hull.pop()
        hull.append(s[i])

    return hull[:-1]


n = int(raw_input())
points = [tuple(map(int, raw_input().split())) for _ in xrange(n)]
cf = convex_hull(points)
print len(cf)
for p in cf:
  print "%d %d"%p

Submission status: Accepted

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

Solution code:
# AOJ CGL_4_A Convex Hull
# Python3 2018.6.22 bal4u

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))  # y座標を優先して昇順、同じならx座標で昇順
	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))

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readlines

def remove(p):
    if len(s) < 2:
        return
    a = s.pop()
    b = s.pop()
    s.append(b)
    s.append(a)

    x1, y1 = a; x0, y0 = b ; x,y = p
    x1 -= x0;y1 -= y0; x -= x0;y -= y0

    if x1 * y < x * y1:
        s.pop()
        remove(p)

    return

lines = input()
#with open("./chapter16/input.txt") as f:
    #lines = f.readlines()

n = int(lines[0])

v = []
for i in range(1, n+1):
    v.append(list(map(int, lines[i].split())))

v = sorted(v, key = lambda x: (x[1], x[0]))
s = deque()
s.append(v[0]);s.append(v[1])


#right side
for k in v[2:]:
    remove(k)
    s.append(k)

v.reverse()
s.append(v[1])

#left side
for k in v[2:]:
    remove(k)
    s.append(k)

s.pop()
le = len(s)
print(le)
for i in range(le):
    print(*s.popleft())

Submission status: Accepted

Solution code:
import math

class Vector:
    def __init__(self,x,y):
        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,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
    
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x

def polygon_andrew_scan(points):
    u = []
    l = []
    if len(points)<3:
        return points
    points.sort(key = lambda p:p.x+p.y*10**-8)
    
    u.append(points[0])
    u.append(points[1])
    l.append(points[-1])
    l.append(points[-2])
    #from IPython.core.debugger import Pdb;
    #Pdb().set_trace()
    for i in range(2,len(points)):
        while len(u)>1 and cross(u[-2]-u[-1],points[i]-u[-1])<0:
            u.pop()
        u.append(points[i])
    #Pdb().set_trace()
    for i in range(2,len(points)):
        while len(l)>1 and cross(l[-2]-l[-1],points[-i-1]-l[-1])<0:
            l.pop()
        l.append(points[-i-1])
        
    return l[::-1]+u[1:-1][::-1]

n = int(input())
p = []

for i in range(n):
    x,y = map(int,input().split())
    p.append(Vector(x,y))
    
convex_points = polygon_andrew_scan(p)

bottom_l = convex_points[0]
start = 0
for i in range(len(convex_points)):
    if convex_points[i].y < bottom_l.y:
        bottom_l = convex_points[i]
        start = i
    elif convex_points[i].y == bottom_l.y:
        if convex_points[i].x<bottom_l.x:
            bottom_l = comvex_points[i]
            start = i
            
m = len(convex_points)      
print(m)
for i in range(start,start+m):
    print('{} {}'.format(convex_points[i%m].x,convex_points[i%m].y))

Submission status: Accepted

Solution code:
"""
TLE
"""
from collections import deque
import math
EPS = 10**(-9)
def is_equal(a,b):
    return abs(a-b) < EPS

def norm(v,i=2):
    ret = 0
    n = len(v)
    for j in range(n):
        ret += abs(v[j])**i
    return math.pow(ret,1/i)

class Vector(list):
    """
    ベクトルクラス
    対応演算子
    +  : ベクトル和 
    -  : ベクトル差
    *  : スカラー倍、または内積
    /  : スカラー除法
    ** : 外積
    += : ベクトル和
    -= : ベクトル差
    *= : スカラー倍
    /= : スカラー除法

    メソッド
    self.norm(i) : L{i}ノルムを計算
    """
    def __add__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) + other.__getitem__(i)
        return self.__class__(ret)
    
    def __radd__(self,other):
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = other.__getitem__(i) + super().__getitem__(i)
        return self.__class__(ret)
    
    def __iadd__(self, other):
        n = len(self)
        for i in range(n):
            self[i] += other.__getitem__(i)
        return self

    def __sub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i) - others.__getitem__(i)
        return self.__class__(ret)

    def __isub__(self, other):
        n = len(self)
        for i in range(n):
            self[i] -= other.__getitem__(i)
        return self

    def __rsub__(self,others):
        n = len(self) 
        ret = [0]*n
        for i in range(n):
            ret[i] = others.__getitem__(i) - super().__getitem__(i)
        return self.__class__(ret)
    
    def __mul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)

    def __rmul__(self,other):
        n = len(self)
        if isinstance(other,list):
            ret = 0
            for i in range(n):
                ret += super().__getitem__(i)*other.__getitem__(i)
            return ret
        else:
            ret = [0]*n
            for i in range(n):
                ret[i] = super().__getitem__(i)*other
            return self.__class__(ret)
    
    
    def __truediv__(self,other):
        """
        ベクトルのスカラー除法
        Vector/scalar
        """
        n = len(self)
        ret = [0]*n
        for i in range(n):
            ret[i] = super().__getitem__(i)/other
        return self.__class__(ret)
    
    def norm(self,i):
        """
        L{i}ノルム
        self.norm(i)
        """
        return norm(self,i)
    
    def __pow__(self,other):
        """
        外積
        self**other
        """
        n = len(self)
        ret = [0]*3
        x = self[:]
        y = other[:]
        if n == 2:
            x.append(0)
            y.append(0)
        if n == 2 or n == 3:
            for i in range(3):
                ret[0],ret[1],ret[2] = x[1]*y[2]-x[2]*y[1],x[2]*y[0]-x[0]*y[2],x[0]*y[1]-x[1]*y[0]
            ret = Vector(ret)
            if n == 2:
                return ret
            else:
                return ret

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

qu = deque()
qd = deque()
qu.append(Ps[0])
qu.append(Ps[1])
qd.append(Ps[0])
qd.append(Ps[1])

for i in range(2,n):
    now_p = Ps[i]
    while 1:
        vul = qu[-1] - qu[-2]
        vus = now_p - qu[-2]
        cross_u = vul**vus
        if cross_u[2] > 0:
            qu.pop()
        else:
            qu.append(now_p)
            break
        if len(qu) < 2:
            qu.append(now_p)
            break

    while 1:
        vdl = qd[-1] - qd[-2]
        vds = now_p - qd[-2]
        cross_d = vdl**vds
        if cross_d[2] < 0:
            qd.pop()
        else:
            qd.append(now_p)
            break
        if len(qd) < 2:
            qd.append(now_p)
            break

y_min_ans = min(qd,key=lambda x:x[1])
min_ind = qd.index(y_min_ans)

print(len(qu)+len(qd)-2)
for i in range(min_ind,len(qd)):
    print(*qd[i])
for i in range(len(qu) - 2,0,-1):
    print(*qu[i])
for i in range(min_ind):
    print(*qd[i])