平面上有n条垂直的,m条水平的线,找到他们组成的长方形rectangle,且这些长方形两两
不相互包含
我的做法是
1、遍历nxm,找到线的所有交点集合,得到一个hash表<point, Tuple<vLine,hLine>> P
2、P.keySet 按照Y,X排序,
3、从P.keySet x P.keySet遍历,每两个不在同一条直线上的点p1,p2,得到一个矩形r,
然后看这个矩形四个顶点是否在hash表P里,且他们对应的vLine,hLine是否相交,这样得
到一个hash表<point, Rectangle>, 每生成一个新的矩形,要看他是否和前面的矩形是
否相互包含。
这里面有两次遍历都比较耗时,1,求所有交点;3、生成一个矩形,还要和前面的矩形判
断是否包含。
看看有什么优化的地方。
--
FROM 120.229.14.*