#6034. 「雅礼集训 2017 Day2」线段游戏

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: 匿名

题目描述

给出若干条线段,用 (x_1, y_2), (x_2, y_2) 表示其两端点坐标,现在要求支持两种操作:

  • 0 x1 y1 x2 y2 表示加入一条新的线段 (x_1, y_2), (x_2, y_2)
  • 1 x0 询问所有线段中, x 坐标在 x_0 处的最高点的 y 坐标是什么,如果对应位置没有线段,则输出 0

输入格式

第一行两个正整数 n m 为初始的线段个数和操作个数。
接下来 n 行,每行四个整数,表示一条线段。
接下来 m 行,每行为一个操作 0 x1 y1 x2 y21 x0

输出格式

对于每一个询问操作,输出一行,为一个实数,当你的答案与标准答案误差不超过 10 ^ {-2} 时,则视为正确。

样例

样例输入

3 4
0 -1 4 1
4 2 7 2
7 1 8 2
1 4
1 3
0 3 3 6 3
1 3

样例输出

2
0.5
3

数据范围与提示

对于 10\% 的数据, n, m \leq 1000
对于另外 20\% 的数据,所有的 1 操作都在 0 操作之后;
对于另外 20\% 的数据,所有线段的两端的 x 坐标都包含所有询问的 x 坐标,你可以将每条线段当做直线处理;
对于 100\% 的数据, 1 \leq n \leq 50000, 1 \leq m \leq 150000 x_1, x_2, y_1, y_2 均为整数, 0 < x_0 \leq 10 ^ 5, -10 ^ 6 \leq x_1, x_2, y_1, y_2 \leq 10 ^ 6