#1823. 一眼丁真
一眼丁真
一眼丁真
题目描述
标题: 一眼丁真 - Problem - QOJ.ac
#8946. 一眼丁真
The problem was used in the following contests:
小 A 和小 S 是 ACM 队友。小 A 的眼睛很大、视力出众,往往能从数据中看出奇怪的规律。
某次训练,小 S 在纸上画了个圆。小 A 看了一眼,说:你这明明是正 17 边形啊!他又拿出许多正多边形图片,让小 S 观察。但小 S 对此毫无头绪,于是他请你帮忙鉴定一下。
具体来说,给定多边形最大边数 n,小 A 采用以下方式生成了平面上的 N 个点:
- 首先,选取一个点 (x,y) 作为中心。这个点可能固定为 (0,0),也可能是在 [−1,1]×[−1,1] 中均匀选取的。
- 随机在 [max(3,n−5),n] 中选取一个整数 k。
- 考虑以 (x,y) 为圆心, 1 为半径的圆。均匀随机选取圆的一个内接正 k 边形。
- 重复 N 次,每次均匀随机选取正 k 边形边界上的一点 u,并把 ˆu=u+N 加入到数据中。这里,N 是一个随机噪声,其两维坐标分别独立遵循以 0 为均值,0.01 为标准差的高斯分布。
- 以上所有随机过程独立。
你需要从这 N 个点中,还原出多边形的边数 k。
输入格式
从标准输入读入数据。
本题有多组测试数据。第一行输入正整数 T,表示测试数据组数。
对于每组数据,第一行输入两个正整数 N,n,表示点数和多边形边数的最大可能值。之后 N 行,每行两个浮点数 ˆux,ˆuy,表示一个点 ˆu 的坐标。输入中所有浮点数均保留 6 位有效数字。
输出格式
输出到标准输出。
对于每组数据,输出一个 k 表示多边形的边数。
样例一
见下发文件。
解释
以下分别是样例第 2,4,5,8 组数据的可视化图像。

子任务
对于所有测试点,T=200,N=1000,3≤n≤30。
本题共十个测试点,每个测试点十分,不捆绑测试。
测试点编号n≤中心的选取方式14在 [−1,1]×[−1,1] 中均匀选取$2固定为 (0,0)$310在 [−1,1]×[−1,1] 中均匀选取4固定为 (0,0)520在 [−1,1]×[−1,1] 中均匀选取6固定为 (0,0)725在 [−1,1]×[−1,1] 中均匀选取8固定为 (0,0)930在 [−1,1]×[−1,1] 中均匀选取10固定为 (0,0)
评分方式
对于每个测试点,若你在至多一组测试数据上答案错误,可以获得全部分数,否则不能获得任何分数。
提示
你可能需要以下数学定义,但无法理解以下内容并不影响你的解题:
一个随机变量 X 遵循均值为 μ、标准差为 σ 的高斯分布 N(μ,σ2) 意味着其概率密度函数为 f(x)=1√2πσe−(x−μ)22σ2.
对于一个概率密度函数为 f(x) 的连续随机变量 X 以及实数 a<b,随机变量 X 生成的随机数落在区间 (a,b) 的概率为 Pr(X∈(a,b))=∫baf(x)dx.
你可能需要以下问题性质:
高斯分布的特点为:其密度从均值往左右以指数速度下降,因此在标准差较小的情况下,随机变量的值高概率与均值相近。例如,在本题的情境中,μ=0,σ=0.01,生成出的随机数的绝对值大于 0.04 的概率约为 6×10−4,大于 0.05 的概率不超过 6×10−7,大于 0.07 的概率不超过 3×10−12。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
(本题数据包未提供小体积样例)