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:
#! /usr/bin/env python3

from typing import List, Tuple, Optional, Generator
from math import sqrt, sin, cos, acos, atan2
from enum import IntEnum

EPS = 1e-10


def float_equal(x: float, y: float) -> bool:
    return abs(x - y) < EPS


class PointLocation(IntEnum):
    COUNTER_CLOCKWISE = 1
    CLOCKWISE = -1
    ONLINE_BACK = 2
    ONLINE_FRONT = -2
    ON_SEGMENT = 0

    def is_online(self):
        return self in [PointLocation.ON_SEGMENT,
                        PointLocation.ONLINE_BACK,
                        PointLocation.ONLINE_FRONT]


class Containment(IntEnum):
    OUTSIDE = 0
    ONLINE = 1
    INSIDE = 2


class Point:

    def __init__(self, x: float=0.0, y: float=0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "Point({}, {})".format(self.x, self.y)

    def __str__(self) -> str:
        return f"{self.x} {self.y}"

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Point):
            return NotImplemented
        return float_equal(self.x, other.x) and \
            float_equal(self.y, other.y)

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

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

    def __mul__(self, k: float) -> 'Point':
        return Point(self.x * k, self.y * k)

    def __rmul__(self, k: float) -> 'Point':
        return self * k

    def __truediv__(self, k: float) -> 'Point':
        return Point(self.x / k, self.y / k)

    def __lt__(self, other: 'Point') -> bool:
        return self.y < other.y \
            if abs(self.x - other.x) < EPS \
            else self.x < other.x

    @staticmethod
    def polar(a: float, r: float) -> 'Point':
        return Point(a * cos(r), a * sin(r))

    def arg(self) -> float:
        return atan2(self.y, self.x)

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

    def abs(self) -> float:
        return sqrt(self.norm())

    def dot(self, other: 'Point') -> float:
        return self.x * other.x + self.y * other.y

    def cross(self, other: 'Point') -> float:
        return self.x * other.y - self.y * other.x

    def is_orthogonal(self, other: 'Point') -> bool:
        return float_equal(self.dot(other), 0.0)

    def is_parallel(self, other: 'Point') -> bool:
        return float_equal(self.cross(other), 0.0)

    def distance(self, other: 'Point') -> float:
        return (self - other).abs()

    def in_side_of(self, seg: 'Segment') -> bool:
        return seg.vector().dot(
            Segment(seg.p1, self).vector()) >= 0

    def in_width_of(self, seg: 'Segment') -> bool:
        return \
            self.in_side_of(seg) and \
            self.in_side_of(seg.reverse())

    def distance_to_line(self, seg: 'Segment') -> float:
        return \
            abs((self - seg.p1).cross(seg.vector())) / \
            seg.length()

    def distance_to_segment(self, seg: 'Segment') -> float:
        if not self.in_side_of(seg):
            return self.distance(seg.p1)
        if not self.in_side_of(seg.reverse()):
            return self.distance(seg.p2)
        else:
            return self.distance_to_line(seg)

    def location(self, seg: 'Segment') -> PointLocation:
        p = self - seg.p1
        d = seg.vector().cross(p)
        if d > EPS:
            return PointLocation.COUNTER_CLOCKWISE
        if d < -EPS:
            return PointLocation.CLOCKWISE
        if seg.vector().dot(p) < 0.0:
            return PointLocation.ONLINE_BACK
        if seg.vector().norm() < p.norm():
            return PointLocation.ONLINE_FRONT
        return PointLocation.ON_SEGMENT


Vector = Point


class Segment:

    def __init__(self,
                 p1: Optional[Point] = None,
                 p2: Optional[Point] = None) -> None:
        self.p1: Point = Point() if p1 is None else p1
        self.p2: Point = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "Segment({}, {})".format(self.p1, self.p2)

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Segment):
            return NotImplemented
        return self.p1 == other.p1 and self.p2 == other.p2

    def vector(self) -> Vector:
        return self.p2 - self.p1

    def reverse(self) -> 'Segment':
        return Segment(self.p2, self.p1)

    def length(self) -> float:
        return self.p1.distance(self.p2)

    def is_orthogonal(self, other: 'Segment') -> bool:
        return self.vector().is_orthogonal(other.vector())

    def is_parallel(self, other: 'Segment') -> bool:
        return self.vector().is_parallel(other.vector())

    def projection(self, p: Point) -> Point:
        v = self.vector()
        vp = p - self.p1
        return v.dot(vp) / v.norm() * v + self.p1

    def reflection(self, p: Point) -> Point:
        x = self.projection(p)
        return p + 2 * (x - p)

    def intersects(self, other: 'Segment') -> bool:
        d0: PointLocation = self.p1.location(other)
        d1: PointLocation = self.p2.location(other)
        d2: PointLocation = other.p1.location(self)
        d3: PointLocation = other.p2.location(self)
        return d0 * d1 * d2 * d3 == 0 or \
            (d0 * d1 == -1 and d2 * d3 == -1)

    def intersection(self, other: 'Segment') -> Point:
        a = self.vector()
        b = other.vector()
        c = self.p1 - other.p1
        s = b.cross(c) / a.cross(b)
        return self.p1 + s * a

    def distance_with_segment(self, other: 'Segment') -> float:
        if not self.is_parallel(other) and \
                self.intersects(other):
            return 0
        else:
            return min(
                self.p1.distance_to_segment(other),
                self.p2.distance_to_segment(other),
                other.p1.distance_to_segment(self),
                other.p2.distance_to_segment(self))


Line = Segment


class Circle:

    def __init__(self,
                 c: Optional[Point] = None,
                 r: float=0.0) -> None:
        self.c: Point = Point() if c is None else c
        self.r: float = r

    def __eq__(self, other: object) -> bool:
        if not isinstance(other, Circle):
            return NotImplemented
        return self.c == other.c and self.r == other.r

    def __repr__(self) -> str:
        return "Circle({}, {})".format(self.c, self.r)

    def cross_point_line(self, line: Line) -> List[Point]:
        proj = line.projection(self.c)
        dist = self.c.distance_to_line(line)
        tan = sqrt(self.r * self.r - dist * dist)
        u = line.vector() / line.vector().abs()
        return sorted([proj - tan * u, proj + tan * u])

    def cross_point_circle(self, other: 'Circle') -> List[Point]:
        d = (other.c - self.c).abs()
        r1 = self.r
        r2 = other.r
        a = acos((r1 * r1 + d * d - r2 * r2) / (2 * r1 * d))
        t = (other.c - self.c).arg()
        return sorted([self.c + Vector.polar(self.r, t + a),
                       self.c + Vector.polar(self.r, t - a)])


class Polygon:
    def __init__(self, vertices: List[Point]) -> None:
        self.vertices = vertices
        self.n = len(vertices)

    def sides(self) -> Generator[Segment, None, None]:
        for i in range(self.n):
            yield Segment(self.vertices[i],
                          self.vertices[(i + 1) % self.n])

    def my_contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0

        prev_l = self.vertices[0].location(ps)
        if prev_l.is_online():
            prev_l = self.vertices[-1].location(ps)

        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            cur_l = s.p2.location(ps)
            if cur_l.is_online() or prev_l == cur_l:
                continue
            if ps.intersects(s):
                count += 1
            prev_l = cur_l

        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

    def contains(self, p: Point) -> Containment:
        ps = Segment(p, Point(100000.0, p.y))
        count = 0

        for s in self.sides():
            if p.location(s) == PointLocation.ON_SEGMENT:
                return Containment.ONLINE
            if s.p1.y > s.p2.y:
                s = s.reverse()
            l1 = s.p1.location(ps)
            l2 = s.p2.location(ps)
            if l1 != PointLocation.COUNTER_CLOCKWISE and \
                l2 == PointLocation.COUNTER_CLOCKWISE and \
                ps.intersects(s):
                count += 1

        return Containment.OUTSIDE if count % 2 == 0 \
            else Containment.INSIDE

    def text_contains(self, p: Point) -> Containment:
        x = False
        for s in self.sides():
            a = s.p1 - p
            b = s.p2 - p
            # print(a, b, a.cross(b), a.dot(b))
            if abs(a.cross(b)) < EPS and a.dot(b) < EPS:
                return Containment.ONLINE
            if a.y > b.y:
                tmp = a
                a = b
                b = tmp
            # print(a, b, a.cross(b))
            if a.y < EPS < b.y and a.cross(b) > EPS:
                x = not x
            # print(x)
        return Containment.INSIDE if x else Containment.OUTSIDE

def half_hull(P):
    S = []
    S.append(P[0])
    S.append(P[1])
    for i in range(2, n):
        while len(S) > 1:
            if (S[-1] - S[-2]).cross(P[i] - S[-1]) >= 0:
                break
            S.pop()
        S.append(P[i])
    return S

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

A = half_hull(sorted(P, key=lambda p: (p.y, p.x)))[:-1] + \
    half_hull(sorted(P, key=lambda p: (p.y, p.x), reverse=True))[:-1]

print(len(A), *A, sep='\n')

Submission status: Accepted

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

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

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

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

# yでソート済を準備しておく
Ay=sorted(A, key=itemgetter(0))
Ay.sort(key=itemgetter(1))

# ベクトルの外積
def cross(a, b):
    x1,y1=a
    x2,y2=b
    return x1*y2-y1*x2

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

def calc(a, b, c):
    # aから見たb,cへ向かうベクトルにする
    v1=sub(b, a)
    v2=sub(c, a)
    return cross(v1, v2)

# 2点間の距離
def get_dist(v1, v2):
    return hypot(v1[0]-v2[0], v1[1]-v2[1])

# アンドリューのアルゴリズム(Monotone Chain)
def monotone_chain(li):
    # 左半分
    # 使う座標を保持
    stack=deque()
    stack.append(li[0])
    stack.append(li[1])
    for i in range(2, N):
        # 1つ前->次 と 1つ前->2つ前 のベクトルで外積をチェックして向きを判定する
        while len(stack)>=2 and calc(stack[-1], li[i], stack[-2])<0:
            # 次が時計回り側にある時は1つ前を外す
            stack.pop()
        # 次が反時計回り側にあればOKなので進める
        stack.append(li[i])
    res=list(stack)[:-1]

    # 右半分(やることは同じ)
    stack=deque()
    stack.append(li[-1])
    stack.append(li[-2])
    for i in range(N-3, -1, -1):
        while len(stack)>=2 and calc(stack[-1], li[i], stack[-2])<0:
            stack.pop()
        stack.append(li[i])
    res+=list(stack)[:-1]

    return res

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

Submission status: Accepted

Solution code:
import cmath
EPS = 1e-10

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

#3点が反時計回りか
#一直線上のときの例外処理できていない→とりあえずT
def CCW(p, q, r):
	one, two = q-p, r-q
	if OuterProduct(one, two) > -EPS:
		return True
	else:
		return False

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

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

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

Submission status: Accepted

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

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

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

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

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

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

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

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

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


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

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

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

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

# 点の進行方向 a -> b -> c
def iSP(a,b,c):
    tmp = sgn((b-a).det(c-a))
    if tmp > 0:   return 1   # 左に曲がる場合
    elif tmp < 0: return -1  # 右に曲がる場合
    else: # まっすぐ
        if sgn((b-a).dot(c-a)) < 0: return -2 # c-a-b の順
        if sgn((a-b).dot(c-b)) < 0: return  2 # a-b-c の順
        return 0 # a-c-bの順

# ab,cd の直線交差
def isToleranceLine(a,b,c,d):
    if sgn((b-a).det(c-d)) != 0: return 1 # 交差する
    else:
        if sgn((b-a).det(c-a)) != 0: return 0 # 平行
        else: return -1 # 同一直線

# ab,cd の線分交差 重複，端点での交差もTrue
def isToleranceSegline(a,b,c,d):
    return sgn(iSP(a,b,c)*iSP(a,b,d))<=0 and sgn(iSP(c,d,a)*iSP(c,d,b)) <= 0

# 2直線の交点 (存在する前提)
def Intersection(a,b,c,d):
    tmp1 = ((b-a)*(c-a)).det(d-c)
    tmp2 = (b-a).det(d-c)
    return a+(tmp1/tmp2)

# 直線ab と 点c の距離
def DistanceLineToPoint(a,b,c):
    return abs(((c-a).det(b-a))/((b-a).abs()))

# 線分ab と 点c の距離
def DistanceSeglineToPoint(a,b,c):
    if sgn((b-a).dot(c-a)) < 0: # <cab が鈍角
        return (c-a).abs()
    if sgn((a-b).dot(c-b)) < 0: # <cba が鈍角
        return (c-b).abs()
    return DistanceLineToPoint(a,b,c)

# 多角形の面積
def PolygonArea(Plist):
    Plist = ConvexHull(Plist)
    L = len(Plist)
    S = 0
    for i in range(L):
        tmpS = (Plist[i-1].det(Plist[i]))/2
        S += tmpS
    return S

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

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

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

    qd.pop()
    qu.popleft()
    hidari = list(qd) + list(reversed(qu)) # 左端開始，左回りPlist
    return hidari

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

Submission status: Accepted

Solution code:
def sgined_area(v0, v1, v2):
    a1 = v1[0] - v0[0]
    a2 = v1[1] - v0[1]
    b1 = v2[0] - v0[0]
    b2 = v2[1] - v0[1]
    return a1*b2 - b1*a2

n = int(input())
vors = [[int(a) for a in input().split() ] for _ in range(n)]
vors.sort(key=lambda v: (v[1], v[0]))

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

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

for v in vors[2:]:
    while len(under) > 1 and sgined_area(under[-2], under[-1], v) < 0:
        under.pop()
    under.append(v)
    
print(len(over) + len(under) - 2)
for v in under[:-1]:
    print(v[0], v[1])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
source = (0,0)
def area(a, b, source):
    return (a[0]-source[0])*(b[1]-source[1]) - (b[0]-source[0])*(a[1]-source[1])

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

# input 
num = int(input())
# initialize
coordinate = []
# input 
for i in range(num):
  coordinate.append(tuple(map(int, input().split())))
result = div_con(coordinate)
# output 
print(len(result))
for item in result:
  print(item[0],item[1])

Submission status: Accepted

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

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

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

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


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

l = j

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

print(len(k))

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

Submission status: Accepted

Solution code:
import math

convex_hull_list = []

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

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

    point_pairs = [(0,0)]*N_vertex

    # ue to sita de tukuru
    convex_hull = [(10001,10001)]*(2*N_vertex)

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

        # gaiseki kara tugi no lower convex_hull youso sagasite ikuzo
        for i in range(0,N_vertex):
            while(k >= 2 and isRight_from_gaiseki(convex_hull[k-2],convex_hull[k-1],point_pairs[i])<0):
                k = k - 1
            convex_hull[k] = point_pairs[i]
            k = k + 1

        t = k + 1
        # gaiseki kara tugi no upper convex_hull youso sagasite ikuzo
        for i in range(N_vertex-1, 0, -1):
            #t = k + 1
            while(k >= t and isRight_from_gaiseki(convex_hull[k-2],convex_hull[k-1],point_pairs[i-1])<0):
                k = k - 1
            #k = k + 1
            convex_hull[k] = point_pairs[i-1]
            k = k + 1
        convex_hull_valid_num = k - 1
        print(convex_hull_valid_num)
        # result
        for i in range(0,convex_hull_valid_num):
            print("{0} {1}".format(convex_hull[i][0],convex_hull[i][1]))

Submission status: Accepted

Solution code:


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


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


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

Submission status: Accepted

Solution code:
import math

EPS = 1e-10


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

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

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

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

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

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

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

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

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

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

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


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


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


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


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


def intersect(p1, p2, p3, p4):
    '''
    p1p2とp3p4の交差判定
    '''
    # t1 = (p1.x-p2.x)*(p3.y-p1.y)+(p1.y-p2.y)*(p1.x-p3.x)
    # t2 = (p1.x-p2.x)*(p4.y-p1.y)+(p1.y-p2.y)*(p1.x-p4.x)
    # t3 = (p3.x-p4.x)*(p1.y-p3.y)+(p3.y-p4.y)*(p3.x-p1.x)
    # t4 = (p3.x-p4.x)*(p2.y-p3.y)+(p3.y-p4.y)*(p3.x-p2.x)
    # return (t1*t2) <= 0.0 and (t3*t4) <= 0.0
    c1 = ccw(p1, p2, p3)*ccw(p1, p2, p4)
    c2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)
    return c1 <= 0.0 and c2 <= 0.0


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


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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# CGL_4_A: Convex Polygon - Convex Hull

from operator import itemgetter


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


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

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

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

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

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


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

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

    convex = convex_hull(ps)

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


if __name__ == '__main__':
    run()