>灵梦惊奇⑨居然算准了她和薛定谔的猫一样的富婆值(不亚于证明上帝不掷骰子) >于是又给⑨出了一个小学二年生的题目,⑨发现这个题目和自己的一个招式很像 >于是⑨对题目使用了「完美的黄金回旋」! (对它使用炎拳罢(悲))
给定平面上 n 个点,找出其中一对点的距离,使得在所有点对中,该距离最小。有一种知名的假算法如下:
一种假算法的实现代码为:(注意该代码没有随机旋转,而是固定旋转)
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 50;
#define D double
struct spot
{
D a[4];
} p[N];
D x, y, x_, y_, z, w, ans;
int n;
bool mmp(const spot &u, const spot &v)
{
return u.a[0] < v.a[0];
}
int main()
{
scanf("%d", &n);
z = sin(1), w = cos(1); //旋转1弧度≈57°
for (int i = 1; i <= n; i++)
{
scanf("%lf%lf", &x, &y);
x_ = x * w - y * z;
y_ = x * z + y * w; //计算旋转后的坐标
p[i].a[0] = x_;
p[i].a[1] = y_;
p[i].a[2] = x;
p[i].a[3] = y; //存下来
}
sort(p + 1, p + n + 1, mmp); //排序
ans = 2e9 + 0.01; //初始化答案
for (int i = 1; i <= n; i++)
for (int j = 1; i + j <= n && j <= 5; j++)
{ //枚举
x = p[i].a[2];
y = p[i].a[3];
x_ = p[i + j].a[2];
y_ = p[i + j].a[3];
z = sqrt((x - x_) * (x - x_) + (y - y_) * (y - y_)); //计算距离
if (ans > z)
ans = z; //更新答案
}
printf("%.12lf\n", ans); //输出
}
现在请你构造一组数据,使得上述代码无法正确解得答案。
输入
本题无输入。
输出
输出一行一个整数 n(1\le n\le 10^5),代表点的数目。
接下来输入 n 行,每行两个实数 x_i,y_i(0\le x_i,y_i\le 10^9) 且小数点位数不超过六位。
你的答案被认为是正确的当且仅当你构造的点对使得上述伪代码输出的答案 ans' 与标准答案 ans 的相对或绝对误差 \dfrac{|ans-ans'|}{\max(ans,1)}\ge 10^{-2}。
来源
2023 SCNUCPC 网络赛 (重现)