题目背景

小 A 喜欢在广场上散步。

有一次在小 A 散步的时候，由于思考得过于投入，他不小心撞在了电线杆上。

于是就有了这道题目（当然是假的）。

题目描述

小 A 和 好友小 Y 站在一个平面上，他们的初始坐标分别是 $(Ax_0,Ay_0)$ 和 $(Bx_0,By_0)$。

当然，站着实在是太无聊了，所以他们会不停地移动。

准确来说，小 A 共有 $n$ 次移动，小 Y 共有 $m$ 次移动。

小 A 在第 $At_{i-1}$ 到第 $At_i$ 时刻会从 $(Ax_{i-1},Ay_{i-1})$ 匀速直线运动到 $(Ax_i,Ay_i)$。

小 Y 在第 $Bt_{i-1}$ 到第 $Bt_i$ 时刻会从 $(Bx_{i-1},By_{i-1})$ 匀速直线运动到 $(Bx_i,By_i)$。

• $At_0=Bt_0=0$。

小 A 还有 $q$ 次询问： 每次询问给出一个浮点数 $c$ 和一个整数 $f$，请求出他们第 $f$ 次相距 $c$ 的时刻。

• 特殊的，如果他们之间相距 $c$ 的时刻有无数个，输出 -2.33。

• 特殊的，如果 $f$ 大于他们之间相距 $c$ 的次数，输出 -4.66。

• 如果不满足上面两个条件，输出他们第 $f$ 次相距 $c$ 的时刻。

输入格式

第一行，三个整数 $n,m,q$ —— $n$ 表示小 A 的移动次数，$m$ 表示小 Y 的移动次数，$q$ 表示询问次数。

第二行，四个两位浮点数 $Ax_0,Ay_0,Bx_0,By_0$ —— 表示小 A 和小 Y 的初始坐标。

接下来 $n$ 行，第 $i$ 行三个两位浮点数 $Ax_i,Ay_i,At_i$ —— 意义见题目描述。

接下来 $m$ 行，第 $i$ 行三个两位浮点数 $Bx_i,By_i,Bt_i$ —— 同上。

接下来 $q$ 行，每行一个两位浮点数 $c$ 和一个整数 $f$ —— 描述一个询问。

输出格式

共 $q$ 个浮点数，表示每个询问的答案。

3 3 10
0.00 0.00 0.00 1.00
-1.00 -1.00 0.20
10.00 10.00 0.41
-4.56 -1.23 1.00
-2.00 -1.00 0.40
-10.00 -10.00 0.41
9.87 6.54 1.00
0.00 1
1.00 1
5.00 1
5.00 3
5.00 4
10.00 2
10.00 6
28.28 1
28.28 2
28.29 1

-4.66
-2.33
0.26970954
0.83836048
-4.66
0.65792852
-4.66
0.40999665
0.41005730
-4.66

提示

「Special Judge」

本题使用 Special judge。

如果你的输出与正确答案的相对误差或绝对误差不超过 $10^{-7}$，将会获得该测试点的满分，否则不得分。建议输出至少 $8$ 位小数。

请不要输出除了题目要求以外的数字，否则可能获得 UKE。

保证没有答案为 $0$ 的情况。

SPJ 如下：

#include "testlib.h"
#define double long double
const double eps=1e-7;
bool Equal(double x,double y){
	return abs(x-y)<=eps||abs((x-y)/y)<=eps;
}
int main(int argc, char* argv[]){
    registerTestlibCmd(argc, argv);
    int n=inf.readInt(),m=inf.readInt(),q=inf.readInt();
    for(int i=1;i<=q;i++){
    	double x=ouf.readDouble(),y=ans.readDouble();
    	if(!Equal(x,y))quitf(_wa,"On line %d the answer is wrong: expected = %.8LF, found = %.8LF",i,y,x);
	}
	quitf(_ok, "The answer is correct."); 
	return 0;
}

「数据范围与约定」

本题使用捆绑测试。

Subtask 编号	$n,m\leq$	$q\leq$	得分
$1$	$5\times 10^2$	$10^3$	$10$
$2$	$2\times 10^4$		$20$
$3$	$4\times 10^4$	$5\times 10^4$	$30$
$4$	$8\times 10^4$	$3\times 10^5$	$40$

对于 $100\%$ 的数据，有 $1\leq n,m\leq 8\times 10^4$，$1\leq q\leq 3\times 10^5$，$At_n=Bt_m\leq 6\times 10^4$，$1\leq f\leq m+n$，$0\leq c\leq 3\times 10^4$。

为保证极端数据下的精度，所有坐标的绝对值不大于 $10^4$。

保证 $At_i<At_{i+1}$，$Bt_i<Bt_{i+1}$，一次移动的时间不超过 $6\times 10^2$。不保证某次移动没有改变位置。

请注意精度误差。

「时间 & 空间限制」

对于第 $1$ 个子任务，时限 $\rm{1s}$；其余子任务时限 $\rm{2.5s}$。

对于第 $1$ 个子任务，空限 $\rm{128MB}$；其余子任务空限 $\rm{256MB}$。

为了卡掉错解，出题人放短了时限，但时限仍在 std 的 $2$ 倍以上。

std 轻微卡常，请注意 I/O/常数优化。

本题开启自动 O2 优化。

「来源」

Sweet Round 04 F。
idea & std：Alex_Wei。