logo AlgoBeat OnlineJudge
登录 注册

#214382. [ROI 2014 Day1] 对撞机 2.0

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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


对撞机是一种用于研究基本粒子碰撞的装置。在其运行过程中,粒子被加速到极高速度。一个专门的探测器可以记录粒子的轨迹,这些轨迹在水平平面上表现为直线。

探测器的上方安装有一台超高速摄像机,其支架可以在水平平面上旋转。摄像机在任意时刻的方向由一条导向直线确定。摄像机可以拍摄任意矩形区域,并且该矩形的某一边必须与导向直线平行。

为了便于分析粒子可能发生的碰撞,要求每一张照片都必须包含截至拍摄时刻的所有轨迹交点。由于摄像机使用的耗材非常昂贵,因此每一张照片的面积必须尽可能小。

你的任务是:给定一系列按时间顺序发生的两类事件:

  • 新的粒子轨迹出现;
  • 摄像机按照指定导向直线拍摄一张照片;

对于每一张照片,求出包含所有轨迹交点的最小矩形区域的面积

输入格式

第一行包含一个整数 ,表示事件总数()。

接下来的 行中,每行描述一个事件。

每个事件包含 5 个元素:

  • 第一个元素为 +,表示出现一条新的轨迹;或为 ?,表示摄像机拍摄一张照片。
  • 随后的 4 个元素为整数 ,表示两个不重合的点的坐标()。
  • 对于 + 事件,这两个点位于该粒子轨迹上,且所有轨迹两两不同。对于 ? 事件,这两个点位于摄像机的导向直线上。

输出格式

设共有 次拍摄事件。

输出 个实数,分别表示每一张照片最小可能的矩形区域面积,输出顺序与拍摄顺序一致。

如果输出的面积为 ,标准答案为 ,则当满足以下条件时,该测试点被认为正确:

样例

样例输入 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

样例输出 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

样例输出 2

0.0
0.0
0.25
0.0000000

数据范围与提示

样例 1 解释

:::align{center} :::

样例 2 解释

:::align{center} :::

数据范围

测试共 组,独立计分,每组 分。下表给出了部分测试的参数信息。

测试点 备注
引导直线平行于坐标轴
所有照片拍摄在所有粒子出现之后