译自 ROI 2014 Day1 T4. Коллайдер 2.0
对撞机是一种用于研究基本粒子碰撞的装置。在其运行过程中,粒子被加速到极高速度。一个专门的探测器可以记录粒子的轨迹,这些轨迹在水平平面上表现为直线。
探测器的上方安装有一台超高速摄像机,其支架可以在水平平面上旋转。摄像机在任意时刻的方向由一条导向直线确定。摄像机可以拍摄任意矩形区域,并且该矩形的某一边必须与导向直线平行。
为了便于分析粒子可能发生的碰撞,要求每一张照片都必须包含截至拍摄时刻的所有轨迹交点。由于摄像机使用的耗材非常昂贵,因此每一张照片的面积必须尽可能小。
你的任务是:给定一系列按时间顺序发生的两类事件:
- 新的粒子轨迹出现;
- 摄像机按照指定导向直线拍摄一张照片;
对于每一张照片,求出包含所有轨迹交点的最小矩形区域的面积。