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:
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   # counter clockwise
        elif cross < 0:
            return 1    # clockwise
        else:           # cross == 0
            dot = self.dot(vec_pt1_to_pt)
            if dot < 0:
                return -2    # online back
            else:       # dot > 0
                if self.abs() < vec_pt1_to_pt.abs():
                    return 2    # online front
                else:
                    return 0    # on segment

    def cross_point(self, other) -> Point:
        d1 = abs(self.cross(Vector(self.pt1, other.pt1)))       # / self.abs()
        d2 = abs(self.cross(Vector(self.pt1, other.pt2)))       # / self.abs()
        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()
        # if vec_abs > (self.r + other.r):
        #     raise AssertionError
        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()
        # if vec_abs > (self.r + other.r):
        #     raise AssertionError

        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)

            #print("pt", pt, "vtx", self.vertices[i], self.vertices[(i+1) % self.num_vertices], "vec", vec_a, vec_b, "dot", dot, "cross", cross)
            if math.isclose(cross, 0.0) and dot <= 0:
                return 1        # on a edge
            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]:
        # leftmost Point
        vertices.sort(key=lambda pt: (pt.x, pt.y))
        convex_full = []
        # form upper convex full
        not_used_vertices = Polygon.append_convex_vertex(vertices, convex_full)

        # form lower convex full
        not_used_vertices.sort(key=lambda pt: (pt.x, pt.y), reverse=True)
        not_used_vertices.append(vertices[0])
        #print(convex_full, not_used_vertices)
        _ = 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()

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

# Andrew's algorithm

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

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

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

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

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

# solve
andrew(P)

Submission status: Accepted

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

Submission status: Runtime Error

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

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

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: Runtime Error

Solution code:
#CGL_4-A Convex Polygon - Convex Hull
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: Runtime Error

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 :
                ph.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: Runtime Error

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

Solution code:
import heapq

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):
    heappush(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: Runtime Error

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 = deque([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 = deque([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: Runtime Error

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 = deque(P[0],P[1])
    print(phU)
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) :
                break
            else :
                del phU[-2]
                if len(phU) == 2 :
                    break
    phL = deque(P[-1],P[-2])
    for p in P[-3::-1]:
        print(phL)
        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: Runtime Error

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 = deque([])
    phU.append(P[0])
    phU.append(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 = deque([])
    phL.append(P[-1])
    phL.append(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
    phL.pop()
    phL.popleft()
    ph = phU + phL
    return ph

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

Submission status: Runtime Error

Solution code:
#CGL_4-A Convex Polygon - Convex Hull
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 = deque([])
    phU.append(P[0])
    phU.append(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 = deque([])
    phL.append(P[-1])
    phL.append(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
    phL.pop()
    phL.popleft()
    ph = phU + phL
    return ph

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

Submission status: Runtime Error

Solution code:
import sys

def isCLKWISE(ph):
    if (ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 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

input = sys.stdin.readlines()
n = int(input[0])
P = map(lambda x: x.split(), _input[1:])
     
Q = ConvexHullScan(P)
Q.reverse()
print(len(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: Runtime Error

Solution code:
import sys

def isCLKWISE(ph):
    if (ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 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

_input = sys.stdin.readlines()
n = int(_input[0])
P = map(lambda x: x.split(), _input[1:])
     
Q = ConvexHullScan(P)
Q.reverse()
print(len(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: Runtime Error

Solution code:
def isCLKWISE(ph):
    return ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) >= 0
      
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 = range(int(input()))
P = []
for i in n:
    P.append([int(x) for x in input().split()])
      
Q = ConvexHullScan(P)
Q.reverse()
print(len(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: Runtime Error

Solution code:
def isCLKWISE(ph):
    return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P.sort()
    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 = range(int(input()))
P = []
for i in n:
    P.append([int(x) for x in input().split()])
      
Q = ConvexHullScan(P).reverse()
print(len(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: Runtime Error

Solution code:
from collections import deque

def isCLKWISE(ph):
    return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
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 = range(int(input()))
P = []
for i in n : P.append([int(x) for x in input().split()])
Q = deque(ConvexHullScan(P))
Q.reverse()
print(len(Q))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
R = Q.rotate(idx)
for r in R : print(r[0],r[1])