Problem:


Convex Hull

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

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

Input

n
x1 y1 
x2 y2
:
xn yn

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

Output

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

Constraints

3 ≤ n ≤ 100000

-10000 ≤ xi, yi ≤ 10000

No point in the P will occur more than once.

Sample Input 1

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

Sample Output 1

5
0 0
2 1
4 2
3 3
1 3

Sample Input 2

4
0 0
2 2
0 2
0 1

Sample Output 2

4
0 0
2 2
0 2
0 1



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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

EPS = 1e-10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def __main():
    n = int(input())
    P = read_polygon(n)
    P_rev = convex_hull(P)
    print(len(P_rev))
    for i in reversed(P_rev):
        print("{0} {1}".format(i.x, i.y))

if __name__ == '__main__':
    __main()

Submission status: Wrong Answer

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


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


def ccw(p1, p2, p3):
    return cross(p2 - p1, p3 - p1)


# http://en.wikipedia.org/wiki/Graham_scan
def graham_scan(p):
    left = min(p, key=operator.attrgetter('real'))
    p.remove(left)

    def sin(target):
        return cross(target - left, 1) / abs(target - left)
    p.sort(key=sin, reverse=True)
    p = [left] + p

    m = 0
    for i in range(1, len(p)):
        while ccw(p[m - 1], p[m], p[i]) < 0:
            if m > 0:
                m -= 1
            elif i == len(p) - 1:
                break
            else:
                i += 1
        m += 1
        p[m], p[i] = p[i], p[m]
    return p[:m + 1]


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

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

Submission status: Wrong Answer

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


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


def ccw(p1, p2, p3):
    return cross(p2 - p1, p3 - p1)


# http://en.wikipedia.org/wiki/Graham_scan
def graham_scan(p):
    left = min(p, key=operator.attrgetter('imag', 'real'))
    p.remove(left)

    def sin(target):
        return cross(target - left, 1) / abs(target - left)
    p.sort(key=sin, reverse=True)
    p = [left] + p

    m = 0
    for i in range(1, len(p)):
        while ccw(p[m - 1], p[m], p[i]) < 0:
            if m > 0:
                m -= 1
            elif i == len(p) - 1:
                break
            else:
                i += 1
        m += 1
        p[m], p[i] = p[i], p[m]
    return p[:m + 1]


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

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

Submission status: Wrong Answer

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


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


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


def ccw(p1, p2, p3):
    return cross(p2 - p1, p3 - p1)


# http://en.wikipedia.org/wiki/Graham_scan
def graham_scan(p):
    left = min(p, key=operator.attrgetter('imag', 'real'))
    # left = min(p, key=operator.attrgetter('real'))
    p.remove(left)

    def cos(target):
        return dot(target - left, 1) / abs(target - left)
    # def sin(target):
    #    return cross(target - left, 1) / abs(target - left)
    p.sort(key=cos, reverse=True)
    p = [left] + p

    m = 0
    for i in range(1, len(p)):
        while ccw(p[m - 1], p[m], p[i]) < 0:
            if m > 0:
                m -= 1
            elif i == len(p) - 1:
                break
            else:
                i += 1
        m += 1
        p[m], p[i] = p[i], p[m]
    return p[:m + 1]


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

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

Submission status: Wrong Answer

Solution code:
from functools import reduce


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


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


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


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

Submission status: Wrong Answer

Solution code:

def clockwise(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) < 0


n = int(input())
vors = [[int(a) for a in input().split() ] for _ in range(n)]
vors.sort()

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

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

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

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

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

Submission status: Wrong Answer

Solution code:

def clockwise(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) < 0


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 not clockwise(over[-2], over[-1], v):
        over.pop()
    over.append(v)
        
under = [vors[0], vors[1]]

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

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

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

Submission status: Wrong Answer

Solution code:
n = input()
ps = [map(int, raw_input().split()) for i in xrange(n)]
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)
qs.pop()
print len(qs)
for x, y in qs:
    print x, y

Submission status: Wrong Answer

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

import enum


EPS = 1e-10


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


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


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


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


def judge_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 clockwise(p0, p1, p2):
        return judge_points_relation(p0, p1, p2) == PointsRelation.clockwise
    if len(ps) < 3:
        return ps
    ps.sort(key=lambda p: p.imag)
    ps.sort(key=lambda p: p.real)
    n = len(ps)
    k = 0
    ch = [None for _ in range(2 * n)]
    for i in range(n):
        while k >= 2 and clockwise(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 clockwise(ch[k - 2], ch[k - 1], ps[i]):
            k -= 1
        ch[k] = ps[i]
        k += 1
    ch = ch[:k - 1]
    return ch


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

import enum


EPS = 1e-10


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


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


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


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


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


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


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

    for i in range(2, points):
        n1 = len(upper)
        if 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)
        if n2 >= 2 and check_ccw(lower[n2 - 2], lower[n2 - 1], _polygon[j]) != -1:
            n2 -= 1
            lower.pop()
        lower.append(_polygon[j])

    lower.reverse()
    upper_size = len(upper)
    for k in range(points - 2, 0, -1):
        if k < upper_size:
            lower.append(upper[k])

    return lower


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)
    for ele in ans:
        print(int(ele.real), int(ele.imag))

Submission status: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

    for i in range(2, points):
        n1 = len(upper)
        if 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)
        if n2 >= 2 and check_ccw(lower[n2 - 2], lower[n2 - 1], _polygon[j]) != -1:
            n2 -= 1
            lower.pop()
        lower.append(_polygon[j])

    lower.reverse()
    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

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

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

    # lower.reverse()
    lower.sort(key=attrgetter('imag', 'real'))
    # print(upper, lower)

    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

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

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

    lower.reverse()
    lower.sort(key=attrgetter('imag', 'real'))
    # print(upper, lower)

    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

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

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

    lower.reverse()
    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

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

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

    lower.reverse()
    if points==3:
        lower.sort(key=attrgetter('imag', 'real'))
    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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: Wrong Answer

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

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

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

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

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

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

import sys
from operator import attrgetter

EPS = 1e-9


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


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


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


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

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

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

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

    lower.reverse()
    lower.sort(key=attrgetter('imag'))
    for k in range(len(upper) - 2, 0, -1):
        lower.append(upper[k])

    return lower


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