Submit Info #56988

Problem Lang User Status Time Memory
Sort Points by Argument pypy3 Kazu1998k AC 1475 ms 93.34 MiB

ケース詳細
Name Status Time Memory
example_00 AC 48 ms 29.81 MiB
max_random_00 AC 1414 ms 92.98 MiB
max_random_01 AC 1462 ms 93.34 MiB
max_random_02 AC 1417 ms 92.84 MiB
near_arg_00 AC 1389 ms 92.35 MiB
near_arg_01 AC 1385 ms 91.97 MiB
near_arg_02 AC 1396 ms 91.97 MiB
near_arg_shuffle_00 AC 1443 ms 92.72 MiB
near_arg_shuffle_01 AC 1475 ms 92.84 MiB
near_arg_shuffle_02 AC 1468 ms 92.34 MiB
only_x_axis_00 AC 52 ms 29.93 MiB
random_00 AC 898 ms 69.01 MiB
random_01 AC 1069 ms 76.85 MiB
random_02 AC 406 ms 45.95 MiB
small_all_00 AC 50 ms 29.93 MiB

from math import sqrt,sin,cos,tan,asin,acos,atan2,pi,floor,gcd def compare(x,y,ep): """ x,y の大小比較をする. ただし, ep の誤差は同一視する. [Input] x,y: float ep: float [Output] x>y: 1 x=y: 0 x<y: -1 """ if x-y>ep: return 1 elif x-y<-ep: return -1 else: return 0 def max_ep(*X): e=-1 for x in X: if x.ep>e:e=x.ep return e class Point(): __slots__=["x","y","id"] ep=1e-9 def __init__(self,x=0,y=0): self.x=x self.y=y self.id=0 def sign(self,a): return compare(a,0,self.ep) #文字列 def __str__(self): return "({}, {})".format(self.x,self.y) __repr__=__str__ #Bool def __bool__(self): return self.sign(self.x)!=0 or self.sign(self.y)!=0 #等号 def __eq__(self,other): return self.sign(self.x-other.x)==0 and self.sign(self.y-other.y)==0 #不等号 def __ne__(self,other): return not self==other #比較(<) def __lt__(self,other): T=self.sign(self.x-other.x) if T: return T<0 else: return self.sign(self.y-other.y)<0 #比較(<=) def __le__(self,other): return self<other or self==other #比較(>) def __gt__(self,other): return other<self #比較(>=) def __ge__(self,other): return other<=self #正と負 def __pos__(self): return self def __neg__(self): return Point(-self.x,-self.y) #加法 def __add__(self,other): return Point(self.x+other.x,self.y+other.y) def __iadd__(self,other): self.x+=other.x self.y+=other.y return self #減法 def __sub__(self,other): return Point(self.x-other.x,self.y-other.y) def __isub__(self,other): self.x-=other.x self.y-=other.y return self #乗法 def __mul__(self,other): x,y=self.x,self.y u,v=other.x,other.y return Point(x*u-y*v,x*v+y*u) def __rmul__(self,other): if isinstance(other,(int,float)): return Point(other*self.x,other*self.y) #除法 def __truediv__(self,other): if other==0: raise ZeroDivisionError return Point(self.x/other,self.y/other) #絶対値 def __abs__(self): return sqrt(self.x*self.x+self.y*self.y) norm=__abs__ def norm_2(self): return self.x*self.x+self.y*self.y #回転 def rotate(self,theta): x,y=self.x,self.y s,c=sin(theta),cos(theta) return Point(c*x-s*y,s*x+c*y) def __iter__(self): yield self.x yield self.y def __hash__(self): return hash((self.x,self.y)) def latticization(self,delta=1e-7): """ 格子点に十分近いならば, その格子点に吸い寄せる""" if abs(self.x-floor(self.x+0.5))<delta and abs(self.y-floor(self.y+0.5))<delta: self.x=floor(self.x+0.5) self.y=floor(self.y+0.5) def normalization(self): a=abs(self) self.x/=a self.y/=a def normal_unit_vector(self): """ 単位法線ベクトルを求める""" assert self d=self.norm() return Point(-self.y/d,self.x/d) def dot(self,other): return self.x*other.x+self.y*other.y def det(self,other): return self.x*other.y-self.y*other.x def arg(self): return atan2(self.y,self.x) def Argument_Sort(L): """ 点を偏角ソートする. L: 点のリスト """ from functools import cmp_to_key ep=max_ep(*L) def position(P): m=compare(P.y,0,ep) if m==-1: return -1 elif m==0 and compare(P.x,0,ep)>=0: return 0 else: return 1 def cmp(P,Q): a=position(P); b=position(Q) if a<b: return -1 elif a>b: return 1 else:return -compare(P.det(Q),0,ep) L.sort(key=cmp_to_key(cmp)) #================================================ import sys input=sys.stdin.readline write=sys.stdout.write N=int(input()) P=[] for _ in range(N): x,y=map(int,input().split()) P.append(Point(x,y)) Argument_Sort(P) write("\n".join(map(lambda p:"{} {}".format(*p),P)))