b*****1
发帖数: 23 | 1 有rand函数生成一个0-1随机分布的数，要求
1. 在一个长方形内产生一个点（均匀分布）easy
2. 有一系列长方形（互不重叠），产生一个，比列按照面积来，比如AB两个面积比为3
:1，那么落在A内比列要75%，然后随机产生一个点
这个也不难，先算各个面积所占比例，用rand函数产生一个随机数，二分法查找落在哪
个区间，然后call 1函数
3. 如果有重叠怎么办? |
b*****1
发帖数: 23 | 2 电面的时候给了几个想法
1. 给一个bounding box, 然后采用拒绝采样，如果很变态的形状会很变态高 比如十字
型交叉
2. 分割成若干个小的然后加入list
三哥面的，本来以为要跪了，最后phone screen还是给过, recruiter说还给了很高的
score
为3
【在 b*****1 的大作中提到】
: 有rand函数生成一个0-1随机分布的数，要求
: 1. 在一个长方形内产生一个点（均匀分布）easy
: 2. 有一系列长方形（互不重叠），产生一个，比列按照面积来，比如AB两个面积比为3
: :1，那么落在A内比列要75%，然后随机产生一个点
: 这个也不难，先算各个面积所占比例，用rand函数产生一个随机数，二分法查找落在哪
: 个区间，然后call 1函数
: 3. 如果有重叠怎么办?
|
r*****s
发帖数: 1815 | 3 线段树扫描线分割成小矩形，然后用2
你的思路是对的
: 电面的时候给了几个想法
: 1. 给一个bounding box, 然后采用拒绝采样，如果很变态的形状会很变
态高 比
如十字
: 型交叉
: 2. 分割成若干个小的然后加入list
: 三哥面的，本来以为要跪了，最后phone screen还是给过, recruiter说
还给了
很高的
: score
: 为3
【在 b*****1 的大作中提到】
: 电面的时候给了几个想法
: 1. 给一个bounding box, 然后采用拒绝采样，如果很变态的形状会很变态高 比如十字
: 型交叉
: 2. 分割成若干个小的然后加入list
: 三哥面的，本来以为要跪了，最后phone screen还是给过, recruiter说还给了很高的
: score
:
: 为3
|
z*********n
发帖数: 1451 | 4 你没说最关键的信息，重叠部分概率是否应该翻倍？
比如两个长方形A B大小一样，他们有一半的面积是重叠的，那A专属一部分，B专属一
部分，还有AB共有一部分，这三部分各占1/3面积。这种情况AB共有部分产生点的概率
是1/2还是1/3?
如果前者，问题很简单啊，完全套2即可。
如果后者，把原来的输入按横坐标排序后，重新纵切一遍，套2就行了。 |
b*****1
发帖数: 23 | 5 不翻倍，明白了，所以拒绝采样可以work但是很费
谢谢楼上两位
【在 z*********n 的大作中提到】
: 你没说最关键的信息，重叠部分概率是否应该翻倍？
: 比如两个长方形A B大小一样，他们有一半的面积是重叠的，那A专属一部分，B专属一
: 部分，还有AB共有一部分，这三部分各占1/3面积。这种情况AB共有部分产生点的概率
: 是1/2还是1/3?
: 如果前者，问题很简单啊，完全套2即可。
: 如果后者，把原来的输入按横坐标排序后，重新纵切一遍，套2就行了。
|
