""" """ import sys from sys import stdin import math def Monotone_Chain(vlis): def upstate(a,b,c): B = (b[0]-a[0],b[1]-a[1]) C = (c[0]-a[0],c[1]-a[1]) return B[1] * C[0] < C[1] * B[0] def downstate(a,b,c): B = (b[0]-a[0],b[1]-a[1]) C = (c[0]-a[0],c[1]-a[1]) return B[1] * C[0] > C[1] * B[0] N = len(vlis) vc = [vlis[i] for i in range(N)] if N >= 3: vc.sort() uv = [] for v in vc: uv.append(v) while len(uv) >= 3 and upstate(uv[-3],uv[-2],uv[-1]): del uv[-2] dv = [] for v in vc: dv.append(v) while len(dv) >= 3 and downstate(dv[-3],dv[-2],dv[-1]): del dv[-2] #print (uv,dv) tmp = dv[1:-1] tmp.reverse() uv += tmp return uv else: return vc def three_points_on_a_line(a,b,c,d,e,f): dx1 = a-c dy1 = b-d dx2 = a-e dy2 = b-f return dx2*dy1 == dx1*dy2 def delete_line3(lis): ret = [] for v in lis: if len(ret) < 3: ret.append(v) else: x,y = ret[-2],ret[-1] if not three_points_on_a_line(x[0],x[1],y[0],y[1],v[0],v[1]): ret.append(v) return ret N = 10**6 lis = [] D = 10**9 for i in range(N): r = (i * 2*math.pi) / N tup = [ int(D * math.cos(r)) , int(D * math.sin(r)) ] assert 0 <= abs(tup[0]) <= D assert 0 <= abs(tup[1]) <= D lis.append(tup) ans = Monotone_Chain(lis) ans.reverse() print (len(ans),file=sys.stderr) ans = delete_line3(ans) print (len(ans)) for tup in ans: print (tup[0],tup[1])