有关数据离散化的小问题
  • 板块学术版
  • 楼主XURUIFAN
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/9 21:29
  • 上次更新2025/1/10 14:16:20
查看原帖
有关数据离散化的小问题
1288333
XURUIFAN楼主2025/1/9 21:29

RT,在一些涉及几何的点坐标离散化的时候常有以下方式存储一个点:x*1e9+yx,y1e9x,y \le 1e9
这个离散化通常而言是对的,好吧我认为是通常。
下面给出理由:
x*1e9+y这种离散化的本质是通过数学方式把x,yx,y首尾链接起来,例如对点(1,2)(1,2)进行离散化,它的结果是1,000,000,0021,000,000,002,相当于把000,000,001000,000,001000,000,002000,000,002拼起来,得到000,000,001,000,000,002000,000,001,000,000,002,去前导00之后就是1,000,000,0021,000,000,002
但是这种离散化是有限制条件的。必须是xxyy同号的情况。
例子非常易得。如点(11,2)(-11,2),离散化结果是10,999,999,998-10,999,999,998,与我们想得到的11,000,000,002-11,000,000,002不同。如果只是结果不同还好说,但这个时候就出现了类似于hashhash冲突的问题:如果另外有一个点是(10,999,999,998)(-10,-999,999,998)呢?对该点进行离散化,则得到10,000,000,000+(999,999,998)=10,999,999,998-10,000,000,000+(-999,999,998)=-10,999,999,998
这时候就很明显,通过离散化我们的程序认为点(10,999,999,998)(-10,-999,999,998)和点(11,2)(-11,2)是同一个点,这就会导致程序出错。而pair或结构体就不会有这个问题
以上是我在做AT_abc265_e时看题解想到的,因为该题的点的坐标是109x,y109-10^9 \le x,y \le 10^9。而这样的话可能以下题解都需要修改成pair的形式:
https://www.luogu.com.cn/article/xgfs9ddx
https://www.luogu.com.cn/article/hwgfhf68
https://www.luogu.com.cn/article/0pwhr5zu
如果有错误欢迎指出

2025/1/9 21:29
加载中...