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