UVA675 Convex Hull of the Polygon

题目描述

给出一个整点多边形 (可能会有**重复的坐标**) $$\left\{(x_0, y_0),\ (x_1,y_1),\ \dots,(x_n,y_n),\ (x_0,y_0)\right\}$$ 求出它的最小凸包.

输入格式

输入包含多组数据, 以**一空行分隔**. 每组数据包含若干行 $x_i, y_i$ (未给出 $n$). 数据保证多边形至少有三个不同的点

输出格式

以若干行 $x_i, y_i$ 的格式输出凸包. 第一个坐标必须是**按输入顺序的第一个是凸包的点**, 且逆时针输出. 每组输出以一个空行分隔, 不要有多余的空行和字符. 可以在 [uDebug](https://www.udebug.com/UVa/675) 上检测格式是否正确