[AdditionalFile5396.zip](file://AdditionalFile5396.zip?type=additional_file)

#5396. 「ROI 2014 Day 1」对撞机 2.0

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

译自 ROI 2014 Day1 T4. Коллайдер 2.0

对撞机是一种用于研究基本粒子碰撞的装置。在运行时，粒子会被加速到极高的速度。一种特殊的探测器可以将粒子的轨迹记录为水平面上的直线。

探测器上方安装了一台超高速相机，相机固定在一个水平旋转的支架上。相机的朝向在每个时刻由一条引导直线确定。相机可以拍摄任意矩形区域，且矩形区域的一条边必须与指定的引导直线平行。

为了分析粒子的潜在碰撞情况，每个照片必须包含所有粒子轨迹的交点。由于相机使用的耗材非常昂贵，因此需要尽量减小每次拍摄的照片面积。

你需要编写一个程序，根据两种类型事件的时序记录：

• 新粒子轨迹的出现；
• 相机按照指定引导直线方向拍摄照片； 计算出每次拍摄时，包含截至该拍摄时刻前出现的所有粒子轨迹交点的最小矩形区域面积。

输入格式

输入文件的第一行包含一个整数 $n$ $(1 \leq n \leq 200000)$，表示事件的总数。

接下来的 $n$ 行描述了各个事件。

每个事件的描述包含五个元素。第一个元素为字符「+」，表示新粒子轨迹的出现；或者为字符「?」，表示相机拍摄照片的事件。接下来的四个元素为整数 $x_1, y_1, x_2, y_2$ $(-10000 \leq x_1, y_1, x_2, y_2 \leq 10000)$，表示两点坐标。对于第一类事件，这两个点位于粒子轨迹上，且所有轨迹均不相同；对于第二类事件，这两个点位于相机引导直线上。

输出格式

假设有 $q$ 次照片拍摄，输出文件应包含 $q$ 个实数，按拍摄顺序依次列出每次拍摄的最小可能照片面积。测试通过的条件是，对于输出的每个面积 $a$，满足 $\frac{|a - b|}{\max(1, b)} \leq 10^{-4}$，其中 $a$ 为参赛者输出的面积，$b$ 为评委的参考答案面积。

样例 1

输入

6
+ 0 0 0 1
+ 0 0 1 0
+ 1 0 0 2
? 0 0 0 1
+ 2 4 3 6
? 0 0 1 1

输出

2.0
3.000

样例 2

输入

7
? 11 4 -7 8
+ -2 -2 1 1
? 0 0 0 1
+ 0 1 1 0
+ 0 2 2 0
? 0 0 0 1
? 0 0 1 1

输出

0.0
0.0
0.25
0.0000000

数据范围与提示

本题包含 $50$ 个独立测试点，每个测试点价值 $2$ 分，总分为 $100$ 分。测试点的评分是独立的，具体限制条件如下表所示：