求问今天网易游戏一道笔试题

2015/9/15镜像同步7 回复

题目链接描述小G一直想做一款超受欢迎的2D MMORPG游戏。碰撞检测系统(collision detection system)是这类型游戏的核心元件之一。它的主要用途在于判断游戏世界中的物体是否有接触。只有准确检测到这种接触的发生，才能触发后续各种的游戏事件。一般每个游戏对象都会以一个或多个几何形状表示，而碰撞检测系统将会通过判断这些几何形状是否有相交，来判断对应的游戏对象是否有所接触。假设我们把游戏中的对象都看作是一个实心矩形，并且这些矩形的边和X轴或者Y轴平行。假设游戏中同时间有N个物体存在，小G想知道，这些物体总共发生了多少次接触。如果两个物体所表示的矩形相交则认为这两个物体发生了接触。两个矩形相交当且仅当这两个矩形有公共点。输入第一行是整数T(T <= 10)，表示下面有T组数据。之后T个数据，每个数据的第一行为数字N <= 40000，表示物体的个数，之后N行，每行四个整数x0, y0, x1, y1 (x0 < x1, y0 > y1)表示矩形左上角和右下角的坐标。坐标的范围为[0...10^9]。输出输出T行，每行对应一个数据的输出结果，表示N个物体两两间总共发生了多少次接触。样例输入 4 2 4 4 10 0 6 3 8 2 3 6 6 8 2 20 20 100 8 1 8 2 6 3 0 2 2 0 0 2 2 0 0 2 2 0 4 0 2 3 0 1 3 5 0 4 6 7 1 5 4 6 3 样例输出 1 0 3 4 普通方法O(N*N)超时，求问这种类似矩形的题目有什么通用的方法吗？

订阅后，新回复会通过你的通知中心匿名送达。

7 条回复

fuxuemingzhu机器人#1 · 2015/9/15

没想到好方法，学习

fuuko机器人#2 · 2015/9/15

扫描线+树状数组，复杂度O(NlogN) 离散化之后把矩形的左右边界按横坐标排序，左面为入事件，右面为出事件，顺序扫描。对于每个事件维护当前纵坐标的两个前缀和s1[n]和s2[n]，分别为此时1..n存在上边界和下边界的个数。每当处理矩形入事件的时候统计s1[下边界]-s2[上边界-1]即为与该矩形相交的次数。

nano123机器人#3 · 2015/9/16

lz可以试试转换成括号检查类似的题目，从横向和纵向分别检查，比如从横向来说，将矩形的左右边界看作括号的左右边界，一个括号成对出现之后才能出现下一个括号，意思是()()()这样是正确的，{()}或者{(})这样都是错的要对边界进行排序吧这是一定的，只是提供个思路哈

winoros机器人#4 · 2015/9/16

扫描线可以看http://www.cnblogs.com/fenshen371/p/3214092.html这个学习

inaadversity机器人#5 · 2015/9/16

多谢LS

teoy机器人#6 · 2015/9/17

就是这么做 2333 【在 fuuko 的大作中提到: 】 : 扫描线+树状数组，复杂度O(NlogN) : 离散化之后把矩形的左右边界按横坐标排序，左面为入事件，右面为出事件，顺序扫描。对于每个事件维护当前纵坐标的两个前缀和s1[n]和s2[n]，分别为此时1..n存在上边界和下边界的个数。每当处理矩形入事件的时候统计s1[下边界]-s2[上边界-1]即为与该矩形相交的次数。

teoy机器人#7 · 2015/9/17

这题扫描线不是重点，后面那步树状数组还是挺巧妙的 @lxyxynt 【在 winoros 的大作中提到: 】 : 扫描线 : 可以看http://www.cnblogs.com/fenshen371/p/3214092.html这个学习