网易游戏笔试题，问一下大家

_chopper

电梯调度
时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
小易家的楼里有部电梯, 他每天都乘坐这部电梯上下楼. 这部电梯和大家常见的电梯一样, 每层电梯口都有一个按钮. 当按下按钮之后, 电梯会升降到这一层并开门. 住户进门之后, 可以选择自己需要去的楼层, 电梯随后会将住户运送到目的楼层, 并开电梯门. 电梯大大方便了楼里居民的生活.

随着使用次数的增多, 小易经常发现, 在按了电梯按钮之后, 电梯却迟迟不来自己的楼层, 这让有时候有急事出门的他等的十分着急. 他想弄明白其中的原因. 经过一番仔细的观察之后，他发现这部电梯的调度的一些规律细节:

      1.电梯的行动是按秒为单位的. 在每一秒开始的时候, 电梯首先处理所有住户的按键需求, 之后才开始在楼层间移动
      2.在每一秒内, 电梯可以上移一楼, 下移一楼, 或停在当前楼层 (因此在每一秒开始的时候, 电梯都是恰好处在某一层的)
      3.电梯会上移或下移到需要的开门的楼层, 一旦经过一个需要开门的楼层, 电梯会开门让住户进出. 如果没有需要开门的楼层, 那么电梯会直接停在当前楼层. 可以假设开门/关门和住户选择目标楼层均不消耗时间
     4.如果电梯楼层之上和之下都有需要开门的楼层, 那么电梯移动的方向取决于上一秒电梯的状态. 如果上一秒电梯处于上升状态, 那么电梯会优先选择上升, 否则电梯会优先选择下降
     5.电梯在第 1 秒开始的时候停在 1 层. 电梯可以到达的最低层为 1 层

现在, 小易拿到了一组数据. 数据中每一项包括三个整数 ti si 和 ei, 表示在第 ti 秒的时候, 第 si 层的住户按了电梯按钮, 并在进电梯之后选择了第 ei 层. 小易希望知道这些住户分别是等待了多久之后才进电梯的. 你可以写一个程序帮助他计算吗?
输入
输入包含多组测试数据.

输入的第一行包含一个整数 T(T ≤ 100), 表示输入中一共包含有 T 组测试数据.

每组测试数据第一行是一个整数 N(N ≤ 50000), 表示该组中一共有 N 项数据. 随后一共有 N 行数据, 其中第 i(0 ≤ i < N) 行数据包含三个整数 ti(1 ≤ ti ≤ 1000000) si(1 ≤ si ≤ 1000000) 和 ei(1 ≤ ei ≤ 1000000, si ≠ ei), 表示第 i 个住户在第 ti 秒的时候, 第 si 层的住户按了电梯按钮, 并在进电梯之后选择了第 ei 层.

对于30%的数据, N ≤ 300, ti ≤ 300.
对于100%的数据，N ≤50000, ti ≤ 1000000.
输出
对于每一组输入, 输出 N 个整数, 每个一行. 其中第 i 个整数表示表示第 i 个住户进电梯的等待时间. 每组数据之后输出一个空行.

样例输入
3
1
1 1 2
1
3 4 5
3
1 10 11
5 4 3
10 8 9
样例输出
0

3

9
13
4


Hint
样例说明
1. 对于第 1 个例子, 电梯第 1 秒开始的时候在 1 层开门, 并且在第 2 秒开始的时候到达 2 层, 住户无需等待.
2. 对于第 2 个例子, 电梯前 2 秒停留在 1 层, 第 3 秒开始的时候从 1 层出发, 并在第 6 秒开始的时候到达 4 层, 住户等待时间为 3 秒.
3. 对于第 3 个例子, 电梯第 1 秒从 1 层出发到 10 层, 在第 5 秒开始的时候到达 5 层, 此时电梯继续保持上升去 10 层接第一个住户 (而不是下降到 4 层接第二个住户). 电梯在第 10 秒的时候到达 10 层接到住户 1, 等待时间为 9 秒. 同理, 电梯在第 11 秒时到达 11 层, 在第 14 秒到达 8 层 (住户 3 等待时间 4 秒), 之后在第 18 秒的时候到达 4 层 (住户 2 等待时间 13 秒)

==================================================================================================

地图分割
时间限制：C/C++语言 2000MS；其他语言 4000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB
题目描述：
在一个大型在线游戏中，一个地图中的玩家和物品的数量可能非常多，如果把所有事件放在同一台服务器上计算，会导致服务器压力过大。
工程师们为了解决这个问题，正在研究一种新的地图实现技术。首先，他们假定原始的大地图为矩形区域，然后把这个地图区域分割成多个小地图区域，每个小地图区域间的各种事件和玩家都分别处理，使得每个小地图区域可以独立计算，从而减小单一服务器的计算压力。
为了验证他们的研究猜想，他们需要先生成大量的随机数据，然后再进行验证。生成随机数据的步骤如下：
1. 随机生成一个w*h大小的初始地图，即地图顶点坐标分别为(0, 0), (w, 0), (w, h), (0, h);
2. 重复以下的分割操作n次：选取一个当前的随机区域，在组成这个区域中的边中，选择两个点，并连结这两个点成为线段，把选取的随机区域分割成两个更小的区域；
最终结果是把原来的初始地图，通过n次切割，变成n+1个小区域。现在他们需要一个程序，用来计算所有这n+1个小区域，面积最大的区域的面积是多少。
输入
输入文件的第一行为一个正整数T，表示测试数据组数。
接下来有T组数据。每组数据第一行为三个正整数，w, h, n，分别表示初始地图的宽和高，以及分割的线段数。接下来以n行，每行包括6个非负整数，s1, x1, y1, s2, x2, y2，(x1, y1)和(x2, y2)分别表示线段的两个端点，s1和s2分别表示第一个点和第二个点的来源，等于0时表示对应的点位于初始地图的边缘，大于0则表示对应的点是从哪个线段中选取的，例如1，表示这个点从第一个输入的线段中选取的。

数据范围：
对于30%的数据文件，满足1 <= w, h <= 1000, 1 <= n <= 100;
对于所有数据文件，满足1 <= T <= 5，1 <= w, h <= 1000000, 1 <= n <= 30000。
对于所有s1i, s2i满足0 <= s1i, s2i < i;
对于所有x1, y1, x2, y2满足0 <= x1, x2 <= w, 0 <= y1, y2 <= h。
输出
对于每个测试数据，输出一行，包含一个浮点数，为面积最大的区域的面积，四舍五入到保留4位小数。

样例输入
3
2 2 2
0 1 0 0 1 2
0 0 1 1 1 1
82 95 5
0 0 64 0 82 64
1 27 64 0 27 95
1 31 64 0 31 95
0 28 95 1 28 64
0 0 66 2 27 66
4 4 5
0 0 0 0 4 4
0 0 0 0 1 4
0 0 0 0 4 1
1 2 2 2 1 4
1 2 2 3 4 1
样例输出
2.0000
5248.0000
3.0000