#P18295. Machine Learning with Penguins

Machine Learning with Penguins

Machine Learning with Penguins

研究者想检查机器学习模型标记出的三维点,是否可能位于一个用来近似直立企鹅的圆柱表面上。

原题中用直圆柱近似企鹅的示意图

原题插图:用圆柱近似企鹅;原照片作者 David Stanley,按 CC BY 2.0 许可使用。此处保留原图。

给定三维空间中的 nn 个点,判断是否存在一个满足下列条件的圆柱:

  • 它是直圆柱,侧面垂直于底面,轴线平行于 zz 轴。
  • 它的下底面位于 xx-yy 平面,即平面 z=0z=0 上。
  • 圆柱的体积严格大于零且有限,即半径和高度均为有限正实数。
  • 给出的所有点都在圆柱的表面上。表面包括侧面以及上下两个完整的圆形底面;底面内部的点也属于表面。

不要求这些点覆盖整个表面,也不要求半径、高度或底面圆心坐标为整数。

输入格式

第一行包含整数 nn(1≤n≤1051\le n\le 10^5)。

接下来 nn 行,每行包含三个整数 x,y,zx,y,z,表示一个三维点,满足

−109≤x,y≤109,0≤z≤109.-10^9\le x,y\le 10^9,\qquad 0\le z\le 10^9.

输入中没有两个完全相同的三维点。不同点可以具有相同的 (x,y)(x,y) 坐标。

输入仅有一组数据。

输出格式

如果存在满足条件的圆柱,输出一行 probably;否则输出一行 not a penguin。

样例 1

5
0 0 0
3 4 1
-3 -4 2
-3 4 3
3 -4 4
probably

样例 2

4
0 6 2
3 4 1
-3 -4 1
-3 4 1
not a penguin

样例 3

2
0 0 0
1 1 0
probably