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

Submission status: Wrong Answer

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):
    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):
    heapq.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: Wrong Answer

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):
    phU = [P[0],P[1]]
    for p in P[2:]:
        heapq.heappush(phU,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]:
        heapq.heappush(phL,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):
    heapq.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: Wrong Answer

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

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

Solution code:
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 True
    return False
      
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: Wrong Answer

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

    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        if isCLKWISE(phU) : continue
        while(True):
            del phL[-2]
            if len(phL) == 2 : break
            else :
                if isCLKWISE(phL) : break

                
                
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = [[int(x) for x in input().split()] for _ in n]
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: Wrong Answer

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)
        if isCLKWISE(phU) : 
            while(True) :
                del phU[-2]
                try :
                    if isCLKWISE(phU) : break
                except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1] :
        phL.append(p)
        if isCLKWISE(phL) :
            while(True) :
                del phL[-2]
                try :
                    if isCLKWISE(phL) : break
                except IndexError : break      
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = [[int(x) for x in input().split()] for _ in n]
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: Wrong Answer

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)
        if not isCLKWISE(phU) : continue
        while(True):
            del phU[-2]
            try:
                if isCLKWISE(phU) : break
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        if not isCLKWISE(phL) : continue
        while(True):
            del phL[-2]
            try:
                if isCLKWISE(phL) : break
            except IndexError : break
      
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = [[int(x) for x in input().split()] for _ in n]
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: Wrong Answer

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 = sorted(P)
    phU = []
    phU.append(P[0])
    phU.append(P[1])
    for p in P[2:] :
        phU.append(p)
        if isCLKWISE(phU) : continue
        while(True) :
            del phU[-2]
            try :
                if isCLKWISE(phU) : break
            except IndexError : break
    phL = []
    phL.append(P[-1])
    phL.append(P[-2])
    for p in P[-3::-1] :
        phL.append(p)
        if isCLKWISE(phL) : continue
        while(True) :
            del phL[-2]
            try:
                if isCLKWISE(phL) : break
            except IndexError : break
        del phL[0]
        del phL[-1]
        ph = phU + phL
        return ph

P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])

Submission status: Wrong Answer

Solution code:
# O(NlgN) time

# build lower hull and upper hull in clockwise, concatenate them get convex hull

import sys
def convexHull(points):
  assert len(points) > 0

  points = sorted(set(points))

  # build lower hull
  lower = []
  for p in points:
    # cross(o, a, b) <= 0 not clockwise
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0: # cross(a,b,c)==c collinear
      lower.pop()
    lower.append(p)
  
  # build upper hull
  upper = []
  for p in points[::-1]:
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0: # if not count collinear <=
      upper.pop()
    upper.append(p)

  # concatenation of the lower and upper hulls gives the convex hull
  print(lower, upper)
  return lower[:-1] + upper[:-1]



# cross product of OA and OB vectors
# U(ou) = u1x + u2y,        V(ov) = v1x + v2y
# UxV = det |u1 u2| = (u1*v2) - (v1*u2) = (u[0]-o[0])*(v[1]-o[1]) - (u[1]-o[1])*(v[0]-o[0])
#           |v1 v2|
def cross(O, A, B):
  return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

# assert convexHull([(i//10, i%10) for i in range(100)]) == [(0, 0), (9, 0), (9, 9), (0, 9)]


if __name__ == '__main__':
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    ans = convexHull(points)
    print(len(ans))
    for x, y in ans:
      print(x, y)

Submission status: Wrong Answer

Solution code:
# O(NlgN) time

# build lower hull and upper hull in clockwise, concatenate them get convex hull

import sys
def convexHull(points):
  assert len(points) > 0

  points = sorted(set(points))

  # build lower hull
  lower = []
  for p in points:
    # cross(o, a, b) <= 0 not clockwise
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0: # cross(a,b,c)==c collinear
      lower.pop()
    lower.append(p)
  
  # build upper hull
  upper = []
  for p in points[::-1]:
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0: # if not count collinear <=
      upper.pop()
    upper.append(p)

  # concatenation of the lower and upper hulls gives the convex hull
  print(lower, upper)
  return lower[:-1] + upper[:-1]



# cross product of OA and OB vectors
# U(ou) = u1x + u2y,        V(ov) = v1x + v2y
# UxV = det |u1 u2| = (u1*v2) - (v1*u2) = (u[0]-o[0])*(v[1]-o[1]) - (u[1]-o[1])*(v[0]-o[0])
#           |v1 v2|
def cross(O, A, B):
  return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

# assert convexHull([(i//10, i%10) for i in range(100)]) == [(0, 0), (9, 0), (9, 9), (0, 9)]


if __name__ == '__main__':
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    ans = convexHull(points)
    print(len(ans))
    for x, y in ans:
      print(int(x), int(y))

Submission status: Wrong Answer

Solution code:
# O(NlgN) time

# build lower hull and upper hull in clockwise, concatenate them get convex hull

import sys
def convexHull(points):
  assert len(points) > 0

  points = sorted(set(points))

  # build lower hull
  lower = []
  for p in points:
    # cross(o, a, b) <= 0 not clockwise
    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) < 0: # cross(a,b,c)==c collinear
      lower.pop()
    lower.append(p)
  
  # build upper hull
  upper = []
  for p in points[::-1]:
    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) < 0: # if not count collinear <=
      upper.pop()
    upper.append(p)

  # concatenation of the lower and upper hulls gives the convex hull
  print(lower, upper)
  return lower[:-1] + upper[:-1]



# cross product of OA and OB vectors
# U(ou) = u1x + u2y,        V(ov) = v1x + v2y
# UxV = det |u1 u2| = (u1*v2) - (v1*u2) = (u[0]-o[0])*(v[1]-o[1]) - (u[1]-o[1])*(v[0]-o[0])
#           |v1 v2|
def cross(O, A, B):
  return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0])

# assert convexHull([(i//10, i%10) for i in range(100)]) == [(0, 0), (9, 0), (9, 9), (0, 9)]


if __name__ == '__main__':
    n = int(input())
    points = [tuple(map(int, input().split())) for _ in range(n)]
    ans = convexHull(points)
    print(len(ans))
    i = min(range(len(ans)), key = lambda i: ans[i])
    for x, y in ans[i:]+ans[:i]:
      print(int(x), int(y))

Submission status: Wrong Answer

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

N = int(input())
data = []
for i in range(N):
    x, y = map(int, input().split())
    data.append((x, y))
data.sort()


#上側の凸包を求める
def isClockwise(a, b):
    ax, ay = a
    bx, by = b
    cross = ax*by - ay*bx
    if cross <= 0:
        return True
    else:
        return False

ans1 = [data[0],data[1]]
for i in range(2,N):
    while True:
        ax, ay = ans1[-2]
        bx, by = ans1[-1]
        cx, cy = data[i]
        flg = isClockwise((bx-ax, by-ay), (cx-bx, cy-by))
        if flg:
            ans1.append(data[i])
            break
        else:
            ans1.pop()
            if len(ans1) == 1:
                ans1.append(data[i])
                break

ans2 = [data[-1],data[-2]]
for i in range(N-3,-1,-1):
    while True:
        ax, ay = ans2[-2]
        bx, by = ans2[-1]
        cx, cy = data[i]
        flg = isClockwise((bx-ax, by-ay), (cx-bx, cy-by))
        if flg:
            ans2.append(data[i])
            break
        else:
            ans2.pop()
            if len(ans2) == 1:
                ans2.append(data[i])
                break

ans2.reverse()
for i in range(len(ans1)-2,0,-1):
    ans2.append(ans1[i])

print(len(ans2))
for xy in ans2:
    x, y = xy
    print(x, y)

Submission status: Wrong Answer

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

n = int(input())

points = []

for i in range(n):
    points.append(tuple(map(int,input().split())))

# print(points)
points.sort()
# print(points)

def is_counter_clockwise(a,b):
    ax, ay = a
    bx, by = b
    cross = ax*by - ay*bx
    if cross > 0:
        return True
    return False


ans = [points[0],points[1]]
for i in range(2,n):
    ax,ay = ans[-2]
    bx,by = ans[-1]
    cx,cy = points[i]
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans.pop()
        if len(ans) == 1:
            break
        ax, ay = ans[-2]
        bx,by = ans[-1]
    ans.append((cx,cy))

# print(ans)

ans2 = [points[-1],points[-2]]
for i in range(n-3,-1,-1):
    ax,ay = ans2[-2]
    bx,by = ans2[-1]
    cx,cy = points[i]
    # print(i,cx,cy)
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans2.pop()
        if len(ans2) == 1:
            break
        ax, ay = ans2[-2]
        bx,by = ans2[-1]
    ans2.append((cx,cy))

# print(ans2)

res = list(set(ans+ans2))

def get_radian(a):
    ax, ay = a
    rad = math.atan2(ay, ax)
    return rad

# print('res')
# print(res)

min_x, min_y = min(res)
# print(min_x, min_y)
rads = []
for point in res:
    x, y = point
    ax = x-min_x
    ay = y-min_y
    rad = get_radian((ax,ay))
    rads.append(rad)
sort_index = sorted(range(len(rads)), key = lambda k:(rads[k],res[k]))
# print(res)
# print(rads)
# print(sort_index)
print(len(res))
for index in sort_index:
    x, y = res[index]
    print(x,y)

Submission status: Wrong Answer

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

n = int(input())

points = []

for i in range(n):
    points.append(tuple(map(int,input().split())))

# print(points)
points.sort()
# print(points)

def is_counter_clockwise(a,b):
    ax, ay = a
    bx, by = b
    cross = ax*by - ay*bx
    if cross > 0:
        return True
    return False


ans = [points[0],points[1]]
for i in range(2,n):
    ax,ay = ans[-2]
    bx,by = ans[-1]
    cx,cy = points[i]
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans.pop()
        if len(ans) == 1:
            break
        ax, ay = ans[-2]
        bx,by = ans[-1]
    ans.append((cx,cy))

# print(ans)

ans2 = [points[-1],points[-2]]
for i in range(n-3,-1,-1):
    ax,ay = ans2[-2]
    bx,by = ans2[-1]
    cx,cy = points[i]
    # print(i,cx,cy)
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans2.pop()
        if len(ans2) == 1:
            break
        ax, ay = ans2[-2]
        bx,by = ans2[-1]
    ans2.append((cx,cy))

# print(ans2)

res = list(set(ans+ans2))

def get_radian(a):
    ax, ay = a
    rad = math.atan2(ay, ax)
    return rad

# print('res')
# print(res)

min_x, min_y = min(res, key=lambda x:(x[1],x[0]))
# print(min_x, min_y)
rads = []
for point in res:
    x, y = point
    ax = x-min_x
    ay = y-min_y
    rad = get_radian((ax,ay))
    rads.append(rad)
sort_index = sorted(range(len(rads)), key = lambda k:(rads[k],res[k]))
# print(res)
# print(rads)
# print(sort_index)
print(len(res))
for index in sort_index:
    x, y = res[index]
    print(x,y)

Submission status: Wrong Answer

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

n = int(input())

points = []

for i in range(n):
    points.append(tuple(map(int,input().split())))

# print(points)
points.sort()
# print(points)

def is_counter_clockwise(a,b):
    ax, ay = a
    bx, by = b
    cross = ax*by - ay*bx
    if cross > 0:
        return True
    return False


ans = [points[0],points[1]]
for i in range(2,n):
    ax,ay = ans[-2]
    bx,by = ans[-1]
    cx,cy = points[i]
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans.pop()
        if len(ans) == 1:
            break
        ax, ay = ans[-2]
        bx,by = ans[-1]
    ans.append((cx,cy))

# print(ans)

ans2 = [points[-1],points[-2]]
for i in range(n-3,-1,-1):
    ax,ay = ans2[-2]
    bx,by = ans2[-1]
    cx,cy = points[i]
    # print(i,cx,cy)
    while is_counter_clockwise((bx-ax,by-ay), (cx-bx,cy-by)):
        ans2.pop()
        if len(ans2) == 1:
            break
        ax, ay = ans2[-2]
        bx,by = ans2[-1]
    ans2.append((cx,cy))

# print(ans2)

res = list(set(ans+ans2))

def get_radian(a):
    ax, ay = a
    rad = math.atan2(ay, ax)
    return rad

# print('res')
# print(res)

min_x, min_y = min(res, key=lambda x:(x[1],x[0]))
# print(min_x, min_y)
rads = []
for point in res:
    x, y = point
    ax = x-min_x
    ay = y-min_y
    rad = get_radian((ax,ay))
    rads.append(rad)
sort_index = sorted(range(len(rads)), key = lambda k:(rads[k],-res[k][0],-res[k][1]))
# print(res)
# print(rads)
# print(sort_index)
print(len(res))
for index in sort_index:
    x, y = res[index]
    print(x,y)

Submission status: Wrong Answer

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

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

Solution code:
from math import sqrt
h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

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 _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = c[:2]

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = c[:2]

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

for x,y in U:
    print(x,y)
for x, y in L:
    if not [x,y] in U:
        print(x,y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

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 _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = c[:2]

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = c[:2]

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))
for x,y in ans:
    print(x, y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

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 _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = c[:2]

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = c[:2]

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))
ans.sort(key=lambda x: (x[1], x[0]))
for x,y in ans:
    print(x, y)

Submission status: Wrong Answer

Solution code:
from math import sqrt
h = {1: 'COUNTER_CLOCKWISE',
       2: 'CLOCKWISE',
       3: 'ONLINE_BACK',
       4: 'ONLINE_FRONT',
       5: 'ON_SEGMENT',}

def dot(a, b):
    return sum([i * j for i,j in zip(a, b)])

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 _abs(a):
    return sqrt(a[0] ** 2 + a[1] ** 2)

def ccw(a, b, c):
    x = sub(b, a)
    y = sub(c, a)
    if cross(x, y) > 0: return 1
    if cross(x, y) < 0: return 2
    if dot(x, y) < 0: return 3
    if _abs(x) < _abs(y): return 4
    return 5

def CCW(a,b,c):
    return h[ccw(a,b,c)]

n = int(input())
c = [list(map(int, input().split())) for i in range(n)]
c.sort(key=lambda x: (x[0], x[1]))
U = c[:2]

for i in range(2, n):
    j = len(U)
    while j >= 2 and CCW(U[-1],U[-2],c[i])  == "COUNTER_CLOCKWISE":
        U.pop()
        j -= 1
    U.append(c[i])

c = c[::-1]
L = c[:2]

for i in range(2, n):
    j = len(L)
    while j >= 2 and CCW(L[-1], L[-2], c[i])  == "COUNTER_CLOCKWISE":
        L.pop()
        j -= 1
    L.append(c[i])

ans = []
for x,y in U:
    ans.append([x,y])
for x, y in L:
    if not [x,y] in U:
        ans.append([x,y])
print(len(ans))
ans.sort(key=lambda x: (x[1], x[0]))
first = ans[0]
i = ans.index(first)
for x,y in ans[i:] + ans[:i]:
    print(x, y)