题目描述

有七个村庄共同争夺一块土地，这块土地的形状是一个凸多边形。

问题的关键在于村庄之间的关系非常紧张：

• 其中有 4 个村庄 彼此关系恶劣，它们之间不能拥有公共边界，最多只能有公共点；
• 另外 3 个村庄 之间的关系也同样恶劣，它们之间也不能拥有公共边界，最多只能有公共点。

关系好的村庄之间并不在意土地面积是否相等，但关系恶劣的村庄之间，哪怕只差一个平方厘米也会争执不休。

土地委员会主席认为，最经济的方案是画出 3 条直线边界 来分割整块土地。原题中给出了一张原理示意图：整块凸多边形被这 3 条直线分成了 7 块，其中 4 块阴影部分面积相等，且彼此不共享边；其余 3 块非阴影部分面积也相等，且彼此不共享边。

三条直线将凸多边形划分为 7 个区域，其中 4 个阴影区域等面积且两两不共边，另外 3 个非阴影区域也等面积且两两不共边。

你的任务是编写程序 partland，给定一个凸多边形，求出这 3 条直线的交点所形成的三角形的 3 个顶点坐标；如果不存在满足条件的划分，则输出 NO。

输入格式

第一行输入一个整数 $N$（$N>2$），表示凸多边形的顶点数。

接下来 $N$ 行，每行输入两个非负整数 $x_i,y_i$，表示多边形顶点坐标。所有顶点按逆时针顺序给出。

输出格式

如果存在解，输出 3 行，每行两个正实数，表示三条边界直线两两相交形成的三角形三个顶点 $T_1,T_2,T_3$ 的坐标。

• 每个坐标的小数点后位数不超过 16 位；
• 同一行的两个数用一个空格分隔。

如果无解，输出一行：

NO

数据范围

原题给出的限制为：

• 顶点坐标均为非负整数，且不超过 $10\,000\,000$；
• $N \le 30000$；
• 至少 10% 的测试满足 $N=3$；
• 20% 的测试中，多边形是平行四边形（因此 $N=4$）；
• 至少 50% 的测试中，坐标不超过 $1000$；
• 80% 的测试满足 $N<100$。

评分方式

本题为部分分题。

• 如果程序正确判断出无解，则该测试点获得满分；

• 如果程序输出了一个划分方案，则计算：

  • 4 个阴影区域的最大面积 $A_{\max}$ 与最小面积 $A_{\min}$；

  • 3 个非阴影区域的最大面积 $B_{\max}$ 与最小面积 $B_{\min}$；

  • 定义

    $$d = \max(A_{\max}-A_{\min},\; B_{\max}-B_{\min}).$$

得分规则如下：

• 若 $d<0.01$，该测试点得满分；
• 否则若 $d<0.1$，该测试点得 80% 分；
• 否则若 $d<1$，该测试点得 50% 分；
• 若 $d \ge 1$，该测试点得 0 分；
• 若实际存在解而程序输出 NO，该测试点也得 0 分。

样例

输入

4
0 0
10 0
10 10
0 10

输出

2.9443006 6.24
7.0561 6.2404
5 3.1206

样例解释

见原题中的 Figure 2。对于该输出，测试点将获得 80% 的分数。

说明

原题要求输出的是形成三条分界直线的三角形三个顶点，而不是 7 块区域本身的面积。