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

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

Time Limit: 3 Sec  Memory Limit: 256 MB  Special Judge
Submit: 1  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

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

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

Input

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

Output

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

Sample Input Copy

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

Sample Output Copy

2
0.5
3

HINT

对于 10% 10\% 10% 的数据,n,m≤1000 n, m \leq 1000 n,m1000
对于另外 20% 20\% 20% 的数据,所有的 1 操作都在 0 操作之后;
对于另外 20% 20\% 20% 的数据,所有线段的两端的 x x x 坐标都包含所有询问的 x x x 坐标,你可以将每条线段当做直线处理;
对于 100% 100\% 100% 的数据,1≤n≤50000,1≤m≤150000 1 \leq n \leq 50000, 1 \leq m \leq 150000 1n50000,1m150000x1,x2,y1,y2 x_1, x_2, y_1, y_2 x1,x2,y1,y2 均为整数,00<x0105,106x1,x2,y1,y2106

Source/Category