P16979 [NWERC 2017] 字形识别 / Glyph Recognition

译自 [Northwestern Europe Regional Contest (NWERC) 2017](http://2017.nwerc.eu) Problem G。 原题许可协议为 CC BY-SA。

你是一名考古学家，正在一处发掘现场工作。你的团队发现了数百块泥板，上面写有某种古代语言的字形。人们对这种语言了解还不多，但你知道它一共只有六种不同的字形，每一种都是一个正多边形的形状，并且有一个顶点指向右侧（见下面图 1）。每个多边形只有边界被刻在泥土上。 :::align{center}  ::: 图 1a：六种字形。 :::align{center}  ::: 图 1b：第一个样例输入。 :::align{center}   ::: 图 1c/1d：将三角形和六边形拟合到第一个样例。三角形的得分更高。 你想立刻开始分析这种语言，因此需要把泥板上的文字转换成机器可读的格式。理想情况下，你会使用 OCR（光学字符识别）工具，但你的笔记本上没有安装这样的工具，而发掘现场也没有互联网连接。 因此，你设计了自己的方案来数字化这些古代文字：对于泥板上的每一个字形，你首先找出若干位于刻痕区域中的采样点，也就是位于多边形边界上的点。根据这些采样点，你再计算六种字形各自的得分，并把得分最高的字形标记为识别结果。 对于给定的角数 $k$（$3 \leq k \leq 8$），得分按如下方式计算。将两个正 $k$ 边形拟合到采样点上，一个在内部，一个在外部，并满足以下条件： - 每个多边形都以原点为中心，也就是说所有顶点到 $(0,0)$ 的距离相等。 - 每个多边形都有一个顶点位于正 $x$ 轴上。 - 内部多边形是在不包含任何采样点的前提下最大的这种多边形。 - 外部多边形是在包含所有采样点的前提下最小的这种多边形。 一个例子见图 1c/1d。对于这个 $k$ 值，得分为 $\frac{A_\text{inner}}{A_\text{outer}}$，其中 $A_\text{inner}$ 和 $A_\text{outer}$ 分别为内部多边形和外部多边形的面积。 给定一组采样点，找出得分最高的字形。

输入包含： - 一行一个整数 $n$（$1 \leq n \leq 1000$），表示采样点数量。 - 接下来 $n$ 行，每行两个整数 $x,y$（$-10^6 \leq x,y \leq 10^6$），表示坐标为 $(x,y)$ 的一个点。 没有采样点位于原点，且所有点互不相同。

Output the optimal number of corners $k$ ($3 \le k \le 8$), followed by the score obtained for that value of $k$. Your answer will be accepted if the absolute error does not exceed $10^{-6}$. If several values of $k$ result in a score that is within $10^{-6}$ of the optimal score, any one of them will be accepted.

【数据规模与约定】 对于所有数据，满足 $1 \leq n \leq 1000$，$-10^6 \leq x,y \leq 10^6$。没有采样点位于原点，且所有采样点互不相同。答案允许绝对误差不超过 $10^{-6}$。