QOJ.ac

QOJ

Time Limit: 10 s Memory Limit: 1024 MB Total points: 100

# 8946. 一眼丁真

Statistics

题目描述

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

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

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

  • 首先,选取一个点 $(x,y)$ 作为中心。这个点可能固定为 $(0, 0)$,也可能是在 $[-1,1] \times [-1,1]$ 中均匀选取的。
  • 随机在 $[\max(3, n-5),n]$ 中选取一个整数 $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=200$,$N=1000$,$3 \le n \le 30$。

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

测试点编号$n \le$中心的选取方式
1$4$在 $[-1,1] \times [-1,1]$ 中均匀选取$
2固定为 $(0,0)$
3$10$在 $[-1,1] \times [-1,1]$ 中均匀选取
4固定为 $(0,0)$
5$20$在 $[-1,1] \times [-1,1]$ 中均匀选取
6固定为 $(0,0)$
7$25$在 $[-1,1] \times [-1,1]$ 中均匀选取
8固定为 $(0,0)$
9$30$在 $[-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}$。