首页 > 其他分享 >线性平面最近点对

线性平面最近点对

时间:2024-09-28 23:11:57浏览次数:6  
标签:个点 int 网格 最近 vec ans 线性 平面 include

讲述一种期望线性复杂度的平面最近点对算法。

  1. 将点打乱
  2. 对于小常数 \(D\),暴力计算前 \(D\) 个点的平面最近点对。
  3. 考虑从前 \(i-1\) 个点推出前 \(i\) 个点的平面最近点对:
    • 设前 \(i-1\) 个点的平面最近点对距离为 \(s\),将平面以 \(s\) 为边长划分成若干网格,用哈希表记录每个网格内的点。
    • 检查第 \(i\) 个点所在的网格及其周围共 \(9\) 个网格内的点是否能更新答案,注意到检查的点的数量是 \(O(1)\) 的,因为每个网格最多有 \(4\) 个点。
    • 若答案更新,重构网格。前 \(i\) 个点的平面最近点对包含第 \(i\) 个点的概率为 \(O\left(\frac{1}{i}\right)\),重构网格的代价为 \(O(i)\),故每个点的期望代价为 \(O(1)\)。

若给定的点有重,可能算法效率会减小,建议特判。

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <unordered_map>
#include <utility>
#include <vector>
#define x first
#define y second
#define M 1000
using namespace std;

int n;
double ans = HUGE_VAL;
vector<pair<int, int>> vec;
unordered_map<uint64_t, vector<pair<int, int>>> grid;

inline uint64_t h(unsigned a, unsigned b) {
  return (uint64_t)a << 32 | (uint64_t)b;
}

void gen() {
  static const int s0 = 290797, m = 50515093;
  int i = 1, last = s0, s;
  for (; (int)vec.size() < n; ++i, last = s) {
    s = (long long)last * last % m;
    if (i & 1)
      vec.push_back(make_pair(last + m, s + m));
  }
}

void pre() {
  int m = min(n, M);
  for (int i = 0; i < m; ++i)
    for (int j = i + 1; j < m; ++j)
      ans = min(ans, hypot(vec[i].x - vec[j].x, vec[j].y - vec[i].y));
}

void remake(int m) {
  grid.clear();
  for (int i = 0; i <= m; ++i) {
    int a = floor(vec[i].x / ceil(ans)), b = floor(vec[i].y / ceil(ans));
    grid[h(a, b)].push_back(make_pair(vec[i].x, vec[i].y));
  }
}

bool has_same() {
  unordered_set<uint64_t> ust;
  for (auto &&[u, v] : vec) {
    uint64_t hs = mapping(u, v);
    if (!ust.insert(hs).second)
      return true;
  }
  return false;
}

int main() {
  mt19937 rnd;
  rnd.seed(random_device()());
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a, b;
    cin >> a >> b;
    vec.push_back(make_pair(a, b));
  }
  if (has_same()) {
    ans = 0;
    goto jump;
  }
  shuffle(vec.begin(), vec.end(), rnd);
  prework();
  remake(min(n, M) - 1);
  for (int i = M; i < n; ++i) {
    int a = floor(vec[i].x / ceil(ans)), b = floor(vec[i].y / ceil(ans));
    double ret = ans;
    for (int dx = -1; dx <= 1; ++dx)
      for (int dy = -1; dy <= 1; ++dy) {
        int s = a + dx, t = b + dy;
        if (grid.count(h(s, t)) == 0)
          continue;
        for (auto &&[u, v] : grid[h(s, t)])
          ret = min(ret, hypot(vec[i].x - u, vec[i].y - v));
      }
    if (ret < ans)
      ans = ret, remake(i);
    else
      grid[h(a, b)].push_back(make_pair(vec[i].x, vec[i].y));
  }
jump:
  cout << fixed << setprecision(4) << ans << "\n";
  return 0;
}

标签:个点,int,网格,最近,vec,ans,线性,平面,include
From: https://www.cnblogs.com/weily09/p/18438619

相关文章

  • 从零开始的数值分析--线性方程组直接解法
    #导入numpy库,用于进行科学计算importnumpyasnp#导入scipy库,用于科学计算和工程计算importscipy#导入matplotlib.pyplot,用于数据可视化importmatplotlib.pyplotasplt#导入sympy库,用于符号数学计算importsympyassp一般来说,我们在解线性方程组是有......
  • 平面最近点对
    #include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5,inf=0x7f7f7f7f;intn;structPoint{doublex,y;}a[N],t[N];boolcmp1(PointA,PointB){if(A.x==B.x)returnA.y<B.y;returnA.x<B.x;}boolcmp2(PointA,PointB){......
  • 8,(经典面试题:分组求topN)Python数分之Pandas训练,力扣,1532. 最近的三笔订单
    学习:知识的初次邂逅复习:知识的温故知新练习:知识的实践应用目录一,原题力扣链接二,题干三,建表语句四,分析五,Pandas解答六,验证七,知识点总结一,原题力扣链接.-力扣(LeetCode)二,题干表:Customers+---------------+---------+|ColumnName|Type|+------......
  • 在线性坐标系中绘制一次函数图象
    本文记述了用Matplotlib在线性坐标系中绘制一次函数图象的例子。代码主体内容如下:fig,ax=plt.subplots(figsize=(8,8))#1x=np.linspace(-4,4,100)y=2*x+1#2ax.plot(x,y,color='b')x=np.linspace(-9,9,1......
  • 三维点云使用pcl实现RANSAC平面分割
    小白每日一练!点云分割分割是将点云划分为多个部分的过程,每个部分代表不同的物体或表面。在这里,我们使用RANSAC算法来识别和分离平面。(以ModelNet40为例)完整代码放在最后面啦!!测试好了可以直接使用!!RANSAC算法RANSAC算法是一种用于从一组包含异常数据的观测数据中估计数学模......
  • 经典单方程计量经济学模型:一元线性回归模型-Eviews实现
            下表为中国内地某年各地区税收Y与国内生产总值的GDP的统计资料。地区YGDP 北京1435.79353.3 天津438.45050.4 河北618.313709.5 山西430.55733.4 内蒙古347.96091.1 辽宁815.711023.5 吉林237.45284.7 黑龙江3357065 上海1975.512188.9 江苏1894.82......
  • 线性基学习DAY2
    今天是第二题学习线性基,让我对线性基的认识更多了,线性基其实就是去处理整个区间异或最值问题的我们来看一下昨天的一道题P4570[BJWC2011]元素昨天其实这题我尝试了两次,一种是普通消元去求解,另一种是高斯消元去求解,但是发现高斯消元的方法只有30分,哪里有问题呢?原来是因为......
  • [转]线性代数库介绍
    1、BLAS基础线性代数程序集(BasicLinearAlgebraSubprograms),基于Fortran实现的基本向量乘法,矩阵乘法的一种科学计算函数库,也是一组向量和矩阵运行的接口规范标淮,规范向量之间的乘法、矩阵之间的乘法等,BLAS实际上是将复杂的矩阵、向量运算简化成类似加减乘法一样的简单计算单元,各......
  • TPS549B22RVFR线性稳压器原装现货PDF数据手册引脚图功能框图参数
    TPS549B22的说明TPS549B22器件是一款紧凑型单通道降压转换器,具有自适应导通时间D-CAP3模式控制。该器件专为高精度、高效率、快速瞬态响应、易于使用、外部元件较少且空间受限的电源系统而设计。该器件采用全差分感应和TI集成FET,高侧导通电阻为4.1mΩ,低侧导通电阻为......
  • 10.解析解方法推导线性回归——不容小觑的线性回归算法
    引言线性回归是许多复杂机器学习模型的基础。作为一种基本的机器学习方法,线性回归提供了清晰的思路和工具,通过理解其推导过程,可以更好地掌握机器学习的基本原理和模型设计。通过阅读本篇博客,你可以:1.学会如何用解析解的方法推导线性回归的最优解2.了解如何判定损失函数是凸......