银行门户网站系统建设方案,公司怎么制作网站,apple官网入口,互动网络游戏公司网站建设题目链接
传送门
思路
我们充分发扬人类智慧#xff1a;
将所有点全部绕原点随机旋转同一个角度#xff0c;然后按 x y x\times y xy 从小到大排序。
根据数学直觉#xff0c;在随机旋转后#xff0c;答案中的三个点在数组中肯定不会离得太远。
所以我们只取每个点…题目链接
传送门
思路
我们充分发扬人类智慧
将所有点全部绕原点随机旋转同一个角度然后按 x × y x\times y x×y 从小到大排序。
根据数学直觉在随机旋转后答案中的三个点在数组中肯定不会离得太远。
所以我们只取每个点向后的 9 9 9 个点来计算答案。
这样速度快得飞起在 1 ≤ n ≤ 2 × 1 0 5 1\le n \le 2\times 10^5 1≤n≤2×105 时都可以在 931ms 内卡过也有可能是我调参不够好欢迎大佬提出更高效的参数。
代码
#include iostream
#include cmath
#include cstdlib
#include algorithmusing 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;
}
