随机排序

标签：直线 10 times 坐标排序随机

题意：给定平面上的 \(n\) 条直线。对于每条直线，求它与其他所有直线构成的交点中，\(x\) 坐标最大的一个交点的坐标。
数据范围：\(n\leqslant 10^5\)，保证每条直线至少和一条直线相交。得分采用 SPJ，即单点得分正相关于该点正确率。
考虑一个简单的事情：斜率越接近的两条直线，它们在 \(y\) 坐标上的“相对距离”减小得越慢。
故考虑用多条 \(l:x=T\) 的竖线去截所有直线。
如果两条直线的斜率很接近，那么在足够多条 \(l:x=T\) 的直线截过之后，至少一条 \(l:x=T\) 上两者的“截距”很接近的概率非常大。
换言之即有很大概率存在一条我们随出来的 \(l:x=T\)，这条直线与 \(l_1,l_2\) 的交点非常接近。
则考虑按与 \(l:x=T\) 的交点将所有直线排序，然后暴力枚举每条直线，向下（不用向上是因为上面的找过你了）找 \(t\) 条直线暴力计算交点，更新答案。
推而广之，想到对 \(l:y=T\) 甚至任意的 \(l:y=kx+b\) 可能也有类似的结论。不妨都做一做，简单起见，\(l:y=kx+b\) 可以直接随一个给出的直线做代替。
总复杂度 \(O(times\times (n\log n+n\times t))\)，其中 \(t\) 为暴力范围。大约可以取 \(times=100,t=20\)。就某老年咸鱼教练的记忆，效果很不错。

题意：给定二维平面上的 \(n\) 个点（考虑到掉精度，都是格点），求其中距离最近的两个点的距离的平方（还是躲掉精度）。
数据范围：
- \(n\leqslant 10^4,2\times 10^5,4\times 10^5(350ms)\) 不等，
- \(x_i,y_i\leqslant 10^9\)。
最后再说一遍，要发扬人类智慧了！
使用伟大的数学直觉：如果数据是随机的，那么最近的两个点的 \(x\) 坐标差的不会太远，可以考虑按 \(x\) 坐标排序然后向后暴力配对。
可是坐标显然不会随机。没关系，我们有人类智慧：随机旋转坐标系！
这样一来，数据的构造性就显著减弱了。
这一做法能通过第二档数据，但会被第三档卡掉，多次旋转的结果我不了解但应该是不行，毕竟时间不够，会 T。
难道就止步于此了吗？不！考虑一下在构造数据中为什么这样做很可能错：因为 \(y\) 坐标相差太大！
所以我们可以随机旋转，然后按 \(x+y\) 为关键字排序！
这一做法的效果没有试过。可能也被卡掉了，emmm...不然应该没必要用最后这种不那么符合数学直觉的方式：
改用 \(x\times y\)！
为啥？...我也不理解...这无论是把点平移到哪个象限，看起来都很不符合数学直觉，但事实就是这样过了。确实得 %。

标签：直线,10,times,坐标,排序,随机
From： https://www.cnblogs.com/weixin2024/p/17053157.html