e****e
发帖数: 1885 | 1 今天被人问到一个问题，想不清楚，大家来讨论讨论：
平面中散布着若干rectangle，顶点坐标为floating，两两之间有可能会发生重叠。问
如何找到矩
形重叠最多的那个区域。要求算法尽量efficient. |
e****e
发帖数: 1885 | 2 如果这个问题是一维的求线段的most overlapping segment，sweeping line应该就能
搞定了，需要nlog(n)的时间。但是现在是二维，我有点想不清楚 |
s********y
发帖数: 58 | |
w********0
发帖数: 1211 | 4 这些矩形的边都平行于x,y轴吗？还是可以旋转成任意角度？
【在 e****e 的大作中提到】
: 今天被人问到一个问题，想不清楚，大家来讨论讨论：
: 平面中散布着若干rectangle，顶点坐标为floating，两两之间有可能会发生重叠。问
: 如何找到矩
: 形重叠最多的那个区域。要求算法尽量efficient.
|
e****e
发帖数: 1885 | 5 但是顶点不是floating的，这个怎么解决
另外，space的efficiency太低。
我想到的是构建hanan grid，然后基于每一个grid统计，但是这样的空间复杂度是n^2
，不知道还
有没有更好的办法
【在 s********y 的大作中提到】
: 平面离散化, 每一个区域统计被覆盖的次数.
|
e****e
发帖数: 1885 | 6 出题人的意图应该是平行于x,y轴的，不过如果能够旋转的话，好像更有意思的咯
【在 w********0 的大作中提到】
: 这些矩形的边都平行于x,y轴吗？还是可以旋转成任意角度？
|
D*****d
发帖数: 1307 | 7 it seems that a rectangle could be represented by center, radius and
diagonal angle.
Just guessing |
g***s
发帖数: 3811 | 8 这个好像是一道当年的acm/icpc试题，不过当时没去做。
给一个所有x,y没有相同值的基本思路：
把所有的矩形的左边和右边按x排序（），总共有2n条边。
初始话一个 hashmap A (float->int) 用来记录：对于记录当前x值下，对于点y，有多
少个重复。
同时，需要保存一个当前排好序的所有y值的队列R
从左向右扫描这2n条边。
对于左边，
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 ++1
× 加入到边的两点的y值加入到A和R里面，A里面的值设为1
对于右边：
× 检查R里面的点，被这条边覆盖。对于这些点，更改A里面的值 --1
× 从A和R删除这两点。
在这个过程中，A里面出现的最大值就是最大overlapping最多的数目
最坏的可能性是O(n^2). |
s********y
发帖数: 58 | 9 离散化是指只存端点, 端点的话是float还是int没有关系啊, space complexity是O(n)
的, n是矩形个数.
2
【在 e****e 的大作中提到】
: 但是顶点不是floating的，这个怎么解决
: 另外，space的efficiency太低。
: 我想到的是构建hanan grid，然后基于每一个grid统计，但是这样的空间复杂度是n^2
: ，不知道还
: 有没有更好的办法
|
m****v
发帖数: 84 | |
|
|
s********y
发帖数: 58 | 11 ACM/ICPC的人吗?还是IOI/NOI/NOIP的?
【在 m****v 的大作中提到】
: 离散化+线段树？
|
g***s
发帖数: 3811 | 12 有多少这样的人在这里？你原来也是？
【在 s********y 的大作中提到】
: ACM/ICPC的人吗?还是IOI/NOI/NOIP的?
|
s********y
发帖数: 58 | |
g*******s
发帖数: 2963 | 14 我也觉得实际应用时离散化比较靠谱。图形application里经常有类似问题～ |
h**********d
发帖数: 4313 | 15 如果矩形都平行于坐标轴可以按边排序
如果可以旋转就用类似数值积分 |
