Logo Quest Online Judge

QOJ

时间限制:1 s 空间限制:256 MB
统计

题目描述

给出若干条线段,用 $ (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 $。