p*****a
发帖数: 147 | 1 这题正解是什么？
- 树结构，O(lgn), how to build tree? 怎么用二分加速？
- 矢量乘法？
- scan all polys, find the min poly that contains the given poly. O(n), easy
to understand and divide to multiple machines.
原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
出最小的包含它的多边形。已知有现成的函数可以判断两个多边形是否相互包含，
iscontained(poly p1, poly p2)。
如何加速？如果在多机的情况下呢？
=> 可以用树结构表示包含的关系。
可以用二分搜索做加速。
多机的话可以range一个机器处理一个区域，另外要考虑前端处理机的负载不要成为瓶
颈，所以让每个机器自己判断此多边形是否包含。 | g***s
发帖数: 3811 | 2 都有了现成的函数，没有必要树结构，也没有必要矢量乘法（这个是用来实现包含函数
的）
× 多core同时对所有多边形判断是否包含给定的多边形，如果包含，得到这个多边形
的最左结点
× 在这些最左结点中找最大的那个，对应的多边形就是了。
easy
【在 p*****a 的大作中提到】
: 这题正解是什么？
: - 树结构，O(lgn), how to build tree? 怎么用二分加速？
: - 矢量乘法？
: - scan all polys, find the min poly that contains the given poly. O(n), easy
: to understand and divide to multiple machines.
: 原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
:
: 10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
: ，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
: 要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
| s*****n
发帖数: 5488 | 3 Rtree. I would be interested to know if they have distributed R tree design.
easy
【在 p*****a 的大作中提到】
: 这题正解是什么？
: - 树结构，O(lgn), how to build tree? 怎么用二分加速？
: - 矢量乘法？
: - scan all polys, find the min poly that contains the given poly. O(n), easy
: to understand and divide to multiple machines.
: 原题见：http://www.mitbbs.com/article_t/JobHunting/31828487.html
:
: 10) 假设有很多多边形，最大的是地球，每一个国家可以认为是一个多边形，每一个省
: ，市，区，小区，楼都可以认为是一个多边形，这些多边形之间要么是相互包含的，
: 要么是互相没有交集的，（不存在overlap的情况）。给出一个多边形，要求写程序求
|
|
