题目链接
思路
我们充分发扬人类智慧:
将所有点全部绕原点随机旋转同一个角度,然后按 $x\times y$ 从小到大排序。
根据数学直觉,在随机旋转后,答案中的三个点在数组中肯定不会离得太远。
所以我们只取每个点向后的 $9$ 个点来计算答案。
这样速度快得飞起,在 $1\le n \le 2\times 10^5$ 时都可以在 931ms 内卡过(也有可能是我调参不够好,欢迎大佬提出更高效的参数)。
Update On 2024.01.31:
加火车头之后从 931ms 一路降到 112ms,赢!
代码
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N = 200010;
int n;
struct Point
{
double x, y;
bool operator< (const Point &t)const
{
return x * y < t.x * t.y;
}
}p[N];
double dis(Point a, Point b)
{
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ )
scanf("%lf%lf", &p[i].x, &p[i].y);
double alpha = 12.4514;
for (int i = 1; i <= n; i ++ )
{
double x = p[i].x + 9, y = p[i].y + 9;
p[i].x = x * cos(alpha) - y * sin(alpha);
p[i].y = x * sin(alpha) + y * cos(alpha);
}
double res = 1e18;
sort(p + 1, p + n + 1);
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= min(n, i + 9); j ++ )
for (int k = j + 1; k <= min(n, j + 9); k ++ )
res = min(res, dis(p[i], p[j]) + dis(p[j], p[k]) + dis(p[i], p[k]));
printf("%.6lf\n", res);
return 0;
}