Background

Little A likes taking a walk in the square.

Once, while Little A was walking, he was thinking too deeply and accidentally ran into a utility pole.

So this problem came out (of course, it is fake).

Problem Description

Little A and his friend Little Y are standing on a plane. Their initial coordinates are $(Ax_0,Ay_0)$ and $(Bx_0,By_0)$, respectively.

Of course, standing still is too boring, so they will keep moving.

More precisely, Little A makes a total of $n$ moves, and Little Y makes a total of $m$ moves.

From time $At_{i-1}$ to time $At_i$, Little A moves from $(Ax_{i-1},Ay_{i-1})$ to $(Ax_i,Ay_i)$ with uniform linear motion.

From time $Bt_{i-1}$ to time $Bt_i$, Little Y moves from $(Bx_{i-1},By_{i-1})$ to $(Bx_i,By_i)$ with uniform linear motion.

• $At_0=Bt_0=0$.

Little A also has $q$ queries. Each query gives a floating-point number $c$ and an integer $f$, asking you to find the time when their distance is $c$ for the $f$-th time.

• Special case: if there are infinitely many times when their distance is $c$, output -2.33.

• Special case: if $f$ is greater than the number of times their distance is $c$, output -4.66.

• Otherwise, output the time when their distance is $c$ for the $f$-th time.

Input Format

The first line contains three integers $n,m,q$, where $n$ is the number of moves of Little A, $m$ is the number of moves of Little Y, and $q$ is the number of queries.

The second line contains four floating-point numbers with two decimal places $Ax_0,Ay_0,Bx_0,By_0$, representing the initial coordinates of Little A and Little Y.

The next $n$ lines: the $i$-th line contains three floating-point numbers with two decimal places $Ax_i,Ay_i,At_i$, as described above.

The next $m$ lines: the $i$-th line contains three floating-point numbers with two decimal places $Bx_i,By_i,Bt_i$, same as above.

The next $q$ lines: each line contains a floating-point number with two decimal places $c$ and an integer $f$, describing a query.

Output Format

Output $q$ floating-point numbers in total, representing the answer to each query.

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

Hint

Special Judge

This problem uses Special Judge.

If the relative error or absolute error between your output and the correct answer is at most $10^{-7}$, you will get full score for that test point. Otherwise, you will get no score. It is recommended to output at least $8$ digits after the decimal point.

Please do not output any numbers other than what the problem asks for, otherwise you may get UKE.

It is guaranteed that there is no case where the answer is $0$.

The SPJ is as follows:

#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;
}

Constraints and Notes

This problem uses bundled testdata.

For $100\%$ of the data, $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$.

To ensure accuracy on extreme testdata, the absolute value of all coordinates is at most $10^4$.

It is guaranteed that $At_i<At_{i+1}$ and $Bt_i<Bt_{i+1}$. The duration of a single move is at most $6\times 10^2$. It is not guaranteed that a move actually changes the position.

Please pay attention to precision errors.

Time & Memory Limits

For Subtask $1$, the time limit is $\rm{1s}$, and for the other subtasks the time limit is $\rm{2.5s}$.

For Subtask $1$, the memory limit is $\rm{128MB}$, and for the other subtasks the memory limit is $\rm{256MB}$.

To eliminate incorrect solutions, the setter shortened the time limit, but it is still more than $2$ times that of the std.

The std is slightly tight on constants. Please pay attention to I/O and constant-factor optimizations.

This problem enables automatic O2 optimization.

Source

Sweet Round 04 F.
Idea & std: Alex_Wei。

Translated by ChatGPT 5