Kanade Doesn't Want to Learn CG
TimeLimit:1000MS MemoryLimit:262144KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
Computational geometry and computer graphics are such hard parts of computer science that Kanade can't manage them. So she doesn't want to learn CG anymore. She goes to play basketball instead.
The only essential equipment in a basketball game is the ball and the hoop ― a flat, rectangular backboard with a basket. We describe the hoop with a side view. Ignoring the thickness, the backboard is considered as a segment parallel to the $y$-axis, and the basket is considered as a segment parallel to the $x$-axis. The right end of the basket is connected to the backboard.
To simplify the model, we consider a basketball as a mass point. Taking only gravity into consideration, if we ignore the basket and the backboard, the trajectory of basketball will be a parabola $y=ax^2+bx+c$ with $a<0$. But the basketball is likely to hit the backboard, resulting in a change in trajectory. We consider the collision between a basketball and the backboard (including the endpoints) as a perfectly elastic collision, which means the velocity on the $x$-axis of the basketball will be reversed, and the velocity on the $y$-axis will remain the same. We ignore the court floor in this problem.
If the basketball passes through the basket (excluding the endpoints) from top to bottom, we consider the shoot is a goal. Once the basketball touches either of the endpoints of the basket, which means it hits the rim, the basketball will be bounced away and cannot make a goal. In addition, according to the rule, a basketball cannot pass through the basket from bottom to top, or it is a violation and cannot be counted as a goal.
Kanade knows the value of $a,b,c$ and the position of the backboard and basket. She would like to know whether the shoot will be a goal if the basketball starts from $x=-114514^{1919810}$ and moves in the positive direction of the $x$-axis.
The only essential equipment in a basketball game is the ball and the hoop ― a flat, rectangular backboard with a basket. We describe the hoop with a side view. Ignoring the thickness, the backboard is considered as a segment parallel to the $y$-axis, and the basket is considered as a segment parallel to the $x$-axis. The right end of the basket is connected to the backboard.
To simplify the model, we consider a basketball as a mass point. Taking only gravity into consideration, if we ignore the basket and the backboard, the trajectory of basketball will be a parabola $y=ax^2+bx+c$ with $a<0$. But the basketball is likely to hit the backboard, resulting in a change in trajectory. We consider the collision between a basketball and the backboard (including the endpoints) as a perfectly elastic collision, which means the velocity on the $x$-axis of the basketball will be reversed, and the velocity on the $y$-axis will remain the same. We ignore the court floor in this problem.
If the basketball passes through the basket (excluding the endpoints) from top to bottom, we consider the shoot is a goal. Once the basketball touches either of the endpoints of the basket, which means it hits the rim, the basketball will be bounced away and cannot make a goal. In addition, according to the rule, a basketball cannot pass through the basket from bottom to top, or it is a violation and cannot be counted as a goal.
Kanade knows the value of $a,b,c$ and the position of the backboard and basket. She would like to know whether the shoot will be a goal if the basketball starts from $x=-114514^{1919810}$ and moves in the positive direction of the $x$-axis.
Input
The first line of input contains one integer $T$ $(1\le T\le 500)$, indicating the number of test cases.
For each test case, the first line contains three integers $a,b,c\ (a \lt 0)$, indicating the parameters of the parabola.
The second line of each test case contains five integers $x_0,x_1,y_0,y_1,y_2$ $(x_0 \lt x_1,y_1 \lt y_0 \lt y_2)$, indicating that the two endpoints of the basket are $(x_0,y_0)$ and $(x_1,y_0)$, and the two endpoints of the backboard are $(x_1,y_1)$ and $(x_1,y_2)$.
It is guaranteed that the absolute value of all integers in the input won't exceed $10^4$.
For each test case, the first line contains three integers $a,b,c\ (a \lt 0)$, indicating the parameters of the parabola.
The second line of each test case contains five integers $x_0,x_1,y_0,y_1,y_2$ $(x_0 \lt x_1,y_1 \lt y_0 \lt y_2)$, indicating that the two endpoints of the basket are $(x_0,y_0)$ and $(x_1,y_0)$, and the two endpoints of the backboard are $(x_1,y_1)$ and $(x_1,y_2)$.
It is guaranteed that the absolute value of all integers in the input won't exceed $10^4$.
Output
For each test case, if the shoot is a goal, output $\texttt{Yes}$ in a single line, otherwise output $\texttt{No}$ in a single line.
SampleInput
4 -1 4 5 3 5 6 5 8 -2 -3 3 -1 0 2 1 4 -1 -9 19 8 10 6 5 8 -1 9 19 8 10 4 3 6
SampleOutput
Yes Yes No No Hint The samples are shown as follows. Segment AB represents the basket, and segment CD represents the backboard.
