「CZYZOI 2017.04.24 JZ 03.08 A」 查询

内存限制: 256 MiB 时间限制: 1000 ms
标准输入输出

题目描述

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

0 x1 y1 x2 y20 \ x1 \ y1 \ x2 \ y2

表 示加入一条新的线段,(x1,y1)(x2,y2)(x1,y1)-(x2,y2)

1 x01 \ x0

询问所有线段中,xx 坐标在 x0x0 处的最高点的 yy 坐标是什么,如果对应位置没有线段,则输出 00

输入格式

第一行两个正整数 N,MN,M 为初始的线段个数和操作个数

接下来 NN 行,每行四个整数,表示一条线段

接下来 MM 行,每行为一个操作” 0 x1 y1 x2 y20 \ x1 \ y1 \ x2 \ y2 ”或” 1 x01 \ x0

输出格式

对于每一个询问操作,输出一行,为一个实数,当你的答案与标准答案误差不超过 10210^{-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.000000
0.500000
3.000000

数据范围与提示

样例解释:

对于 10%10\% 的数据:n,m1000n,m\le1000

另外 20%20\% 的数据:所有的 11 操作都在 00 操作之后

另外 20%20\% 的数据:所有线段的两端的 xx 坐标都包含所有的询问的 xx 坐标,你可以将每条线段当做直线处理

对于 100%100\% 的数据:n50000,m150000n\le50000,m\le150000x1,x2,y1,y2,x0x1,x2,y1,y2,x0 均为整数,0<x0105,106x1,x2,y1,y21060<x0\le 10^5, -10^6\le x1,x2,y1,y2\le 10^6