首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
拉钩
V2EX  ›  问与答

问个算法问题。。。。。。。

  •  
  •   hyousan · 8 天前 · 799 次点击

    有 n 个点和 n 个矩形 矩形和矩形之间可能会有重叠 点用 x,y 来表示 矩形用 x,y,w,h 表示 要求判断:任意一个点都能落在某个矩形里面,且任意一个矩形都至少包含一个点 最好能用 python 实现 有没有什么高效点的办法?

    5 回复  |  直到 2018-12-08 09:33:45 +08:00
        1
    bravecarrot   8 天前 via iPhone   ♥ 1
    表达能力堪忧 。 “要求判断”:后面不应该是一个命题吗? 并没有说清楚
        2
    Xs0ul   8 天前 via Android
    n 是个什么数量级?既然矩形不带角度,那直接 x y 轴比大小也就是 n 方复杂度。
        4
    aheadlead   8 天前 via iPhone
    2000 ?代码 x2
        5
    wnjxyk   8 天前 via iPhone   ♥ 1
    理解一下 Problem Statements,有 n 个点(x, y)、m 个矩形(x, y, w, h),试问当前图形是否满足 每个点都至少被一个矩形包含 且 每个矩形都包含至少一个点。

    假设 n 与 m 都是 1e5 的数量级别的,这个问题可以使用 O(nlogn)的复杂度解决。我们分`每个点至少被一个矩形包含`与`每个矩形都至少包含一个点`这两个部分解决。

    首先的首先,如果坐标的数值范围大的可怕,坐标离散化是必须的。

    每个点至少被一个矩形包含:
    这个问题可以使用扫描线+树状数组(区间修改单点查询)解决。
    我们把矩形拆成(x, y)-(x+w, y)的入边与(x, y+h)-(x+w,y+h)的出边两种。然后把入边、出边与点混在一起按照 y 的值排序(如果点和边的 y 值相同,那么要保证入边<点<出边这种顺序)。
    按照 y 值从小到大的顺序便利这个对象组,当遇到一个入边(x, y)-(x+w, y)的时候,我们对树状数组的[x, x+w]范围区间+1,遇到一个出边(x, y)-(x+w, y)的时候,我们对树状数组的[x, x+w]范围区间-1。
    当遇到点(x, y)的时候,我们查询树状数组位置 x 的值,假设为 p,就表示这个点就被 p 个矩形包含。如果 p=0,那就 GG 啦,直接返回 NO。

    每个矩形都至少包含一个点:
    这个问题,我们直接使用可持久化线段树来解决。
    我们把矩形(x, y, w, h)的排序关键值设为 y+h,点(x, y)的排序关键值设为 y,然后把点和矩形混在一起排序(如果关键值相同,我们保证点<矩形)
    接下来,我们建立一颗可持久化线段树 tree_0,然后关键值从小到大的顺序便利这个对象组。每遍历一个新的离散化之后的 y 值 y0,我们就从 tree_{y}创建一个新的可持久化线段树 tree_{y0+1}。如果当前是一个点(x, y),我们对当前可持久化数据结构的 x 位置+1,如果当前是一个矩形(x, y, w, h),我们在 tree_{y+h}-tree_{y-1}这个线段树上查询区间[x, x+w]的和 p,p 表示这个矩形包含点的数量,如果 p=0 就 GG 啦,返回 NO。

    如果这两个条件都满足就 YES 了。
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2191 人在线   最高记录 4019   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.1 · 16ms · UTC 14:44 · PVG 22:44 · LAX 06:44 · JFK 09:44
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1