背景

译自 Northwestern Europe Regional Contest (NWERC) 2017 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)$ 的一个点。

没有采样点位于原点，且所有点互不相同。

9
-4 -1
-4 6
-3 -6
-3 4
0 -4
2 -3
2 3
5 1
7 0

3 0.5625000000

4
1 0
0 1
-1 0
0 -1

8 1.0000000000

提示

【数据规模与约定】

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