问题描述

一个封闭多边形是由有限条线段围成的图形，这些线段的交点称为多边形的顶点。当从多边形的任意一个顶点出发，沿着每条边界线段恰好遍历一次后，会回到起始顶点。

一个封闭多边形称为凸多边形，如果连接多边形内任意两点的线段都完全位于多边形内部。图1展示了一个凸多边形和一个非凸多边形的例子。（直观地说，封闭多边形是凸的，当且仅当其边界没有“凹陷”。） 本问题的研究对象是坐标平面内的一个封闭凸多边形，其中一个顶点是原点（(x = 0), (y = 0)）。图2展示了一个例子。这样的多边形具有以下两个对问题重要的性质：

1. 顶点分布性质：多边形的顶点将位于坐标平面的四个象限中的三个或更少的象限内。在图2的例子中，没有顶点位于第二象限$(x < 0), (y > 0)$。

2. 斜率排序性质：假设“沿着”多边形“旅行”：从原点 $(0, 0)$ 出发，恰好访问其他所有顶点一次，最后回到原点。当访问每个顶点（除了原点）时，绘制连接当前顶点与原点的对角线，并计算这条对角线的斜率。然后，在每个象限内，这些斜率将形成一个单调递增或单调递减的序列，即它们是有序的。图3说明了这一点。

输入

输入列出了坐标平面内一个封闭凸多边形的顶点。输入的行数至少为3，最多为50。每行包含一个顶点的 $x$ 和 $y$ 坐标。每个 $x$ 和 $y$ 坐标是范围 $-999$ 到 $999$ 的整数。输入的第一行的顶点是原点，即 $x = 0$ 且 $y = 0$。否则，顶点可能是乱序的。除了原点外，没有顶点位于 $x$ 轴或 $y$ 轴上。没有三个顶点是共线的。

输出

输出按逆时针方向沿着多边形边界旅行的顶点顺序，原点 $(0, 0)$ 是输出的第一行。每个顶点在输入中出现一次，输出格式为$(x, y)$。

示例输入 1

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10

示例输出 1

(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)

来源

Rocky Mountain 2004