Skip to content

1304: Probabilistic killer

题目

题目描述

随机化大师博先生认为 Closest pair 一题非常简单,因此他随手设计了如下算法来通过这个题:

  1. 均匀随机地从 $[0, \pi)$ 中选择一个角度 $\theta_0$,作为初始角;
  2. 接下来重复 $T$ 次,第 $k$ 次的角度为 $\theta_k = \theta_0 + \frac {k-1} {T} \pi$;将所有点从初始坐标绕原点逆时针旋转 $\theta_k$ 度并按照 $x$ 轴排序,计算相邻两个点之间的距离。
  3. 输出 $T$ 次计算结果中出现过的距离最小值。

霏老师觉得博先生的做法是搞笑的,并请来了你构造数据卡掉博先生的做法。

Input

输入一个数,$T (1 \leq T \leq 400)$,表示博先生的程序此时采用的参数。

Output

你需要按照 Closest pair 一题的输入格式输出一组数据。

输出第一行为一个正整数 $n (2 \leq n \leq 4\times10^5)$,表示点数。

接下来 $n$ 行,第 $i$ 行为用空格隔开的整数 $x_i, y_i (-10^7 \leq x_i, y_i \leq 10 ^ 7)$,表示 $p_i = (x_i, y_i)$。

你的输出中,不应当包含两个坐标完全相同的点。

How do we judge your answer

本题有 $20$ 组测试点,每组测试点 $5$ 分。

对于第 $i$ 组数据,

  1. $T=i ^ 2$;
  2. 你输出的 $n$ 应当满足: $2 \leq n \leq \lfloor 4\times 10^5 / T\rfloor $。$i= 20$ 时,$n \leq 1000$ 。

对于你的输出,我们将采用如下方法进行测试:

  1. 首先使用正确的最近点对算法计算正确答案。
  2. 固定一个隐藏的随机种子 $\mathrm{SEED}_i$,使用随机数生成器生成 $ 20$ 个初始角度运行博先生的程序。
  3. 如果你成功让博先生的程序输出错误至少 $2$ 次,你就赢了。

作为参考,运行一次 $T = 1$ 的正确率降低至 $1 / 500$ 时,你有 $>0.99$ 的概率通过最后一组测试数据。

Constraints

Time Limit: 3s

Memory Limit: 128MB

Sample Input

txt 1

Sample Output

txt 3 0 0 0 1 0 2

Note

很难不发现样例输出(除了格式)是完全错误的:由于 $(1, 2)$ $(2, 3)$ 的距离均为 $1$,因此所有排列均存在相邻两个点距离为 $1$。评测器会非常肯定地拒绝掉这个输入。

请注意,尽管概率测度是 $0$,实际中仍可能存在旋转后 $x$ 坐标相同的点对,此时排序算法可能返回任意顺序。

你可以参考这份代码来了解博先生算法的细节,其中 TSEED 将在评测时被更改。

```cpp

include

using namespace std; const int T = 10; const int SEED = 114514; const int N = 4e5; const long double pi = acosl(-1); int n, X[N], Y[N]; struct point { long double x, y; int i; bool operator < (const point &a) const { return x < a.x; } long long distance_2(const point &a) { return (long long)(X[a.i] - X[i]) * (X[a.i] - X[i]) + (long long)(Y[a.i] - Y[i]) * (Y[a.i] - Y[i]); } }; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> X[i] >> Y[i]; long long ans = LLONG_MAX; mt19937 rng(SEED); uniform_real_distribution distribution(0, pi); long double theta = distribution(rng); for (int i = 0; i < T; i++) { vector < point > a; long double angle = theta + pi * i / T; for (int j = 0; j < n; j++) { long double x = X[j], y = Y[j]; long double nx = cos(angle) * x + sin(angle) * y, ny = -sin(angle) * x + cos(angle) * y; a.push_back({nx, ny, j}); } sort(a.begin(), a.end()); for (int j = 1; j < n; j++) { ans = min(ans, a[j - 1].distance_2(a[j])); } } cout << ans << endl; } ```

One more thing ...

你能用一个错误的做法冲过 Closest pair 吗?

我们准备了很强的数据,欢迎尝试!

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!