QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 1024 MB Total points: 100
[0]
统计

题目描述

小 A 和小 S 是 ACM 队友。小 A 的眼睛很大、视力出众,往往能从数据中看出奇怪的规律。

某次训练,小 S 在纸上画了个圆。小 A 看了一眼,说:你这明明是正 17 边形啊!他又拿出许多正多边形图片,让小 S 观察。但小 S 对此毫无头绪,于是他请你帮忙鉴定一下。

具体来说,给定多边形最大边数 n,小 A 采用以下方式生成了平面上的 N 个点:

  • 首先,选取一个点 (x,y) 作为中心。这个点可能固定为 (0,0),也可能是在 [1,1]×[1,1] 中均匀选取的。
  • 随机在 [max 中选取一个整数 k
  • 考虑以 (x, y) 为圆心, 1 为半径的圆。均匀随机选取圆的一个内接正 k 边形。
  • 重复 N 次,每次均匀随机选取正 k 边形边界上的一点 u,并把 \hat u=u+\mathcal N 加入到数据中。这里,\mathcal N 是一个随机噪声,其两维坐标分别独立遵循以 0 为均值,0.01 为标准差的高斯分布。
  • 以上所有随机过程独立。

你需要从这 N 个点中,还原出多边形的边数 k

输入格式

从标准输入读入数据。

本题有多组测试数据。第一行输入正整数 T,表示测试数据组数。

对于每组数据,第一行输入两个正整数 N,n,表示点数和多边形边数的最大可能值。之后 N 行,每行两个浮点数 \hat u_x, \hat u_y,表示一个点 \hat u 的坐标。输入中所有浮点数均保留 6 位有效数字。

输出格式

输出到标准输出。

对于每组数据,输出一个 k 表示多边形的边数。

样例一

见下发文件。

解释

以下分别是样例第 2,4,5,8 组数据的可视化图像。

img

子任务

对于所有测试点,T=200N=10003 \le n \le 30

本题共十个测试点,每个测试点十分,不捆绑测试

测试点编号n \le中心的选取方式
14[-1,1] \times [-1,1] 中均匀选取$
2固定为 (0,0)
310[-1,1] \times [-1,1] 中均匀选取
4固定为 (0,0)
520[-1,1] \times [-1,1] 中均匀选取
6固定为 (0,0)
725[-1,1] \times [-1,1] 中均匀选取
8固定为 (0,0)
930[-1,1] \times [-1,1] 中均匀选取
10固定为 (0,0)

评分方式

对于每个测试点,若你在至多一组测试数据上答案错误,可以获得全部分数,否则不能获得任何分数。

提示

你可能需要以下数学定义,但无法理解以下内容并不影响你的解题:

一个随机变量 X 遵循均值为 \mu、标准差为 \sigma 的高斯分布 \mathcal N(\mu, \sigma^2) 意味着其概率密度函数为 f(x) = \frac{1}{\sqrt{2 \pi} \sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}. 对于一个概率密度函数为 f(x) 的连续随机变量 X 以及实数 a < b,随机变量 X 生成的随机数落在区间 (a,b) 的概率为 \Pr(X \in (a,b)) = \int_a^b f(x) dx.

你可能需要以下问题性质:

高斯分布的特点为:其密度从均值往左右以指数速度下降,因此在标准差较小的情况下,随机变量的值高概率与均值相近。例如,在本题的情境中,\mu = 0\sigma = 0.01,生成出的随机数的绝对值大于 0.04 的概率约为 6 \times 10^{-4},大于 0.05 的概率不超过 6 \times 10^{-7},大于 0.07 的概率不超过 3 \times 10^{-12}