Intersection

Interview

Time limit1sMemory limit128 MB

Summary

Decide, for each test case, whether a line segment and an axis-aligned rectangle share at least one point, including degenerate rectangles.

Level: Medium6 of 10
Topics: Geometry, Implementation, Math, Brute force
Solved: No attempts yet

Problem

Write a program that determines whether a given line segment and rectangle intersect.

For example, suppose the segment has start point $(4, 9)$ and end point $(11, 2)$ , and the rectangle has one corner at $(1, 5)$ and the opposite corner at $(7, 1)$ . In this case the segment and the rectangle do not intersect.

The segment and the rectangle intersect if they share at least one point. All coordinates given in the input are integers whose absolute value is at most $50$ , but the point of intersection need not have integer coordinates. The rectangle's area may be $0$ (that is, it may degenerate to a segment or a single point).

Input

The first line contains the number of test cases $T$ . Each test case is given on a single line as eight space-separated integers xstart ystart xend yend xleft ytop xright ybottom.

$(xstart, ystart)$ is the segment's start point and $(xend, yend)$ is its end point.
$(xleft, ytop)$ and $(xright, ybottom)$ are the coordinates of two opposite corners of the rectangle.

The words left, right, top, and bottom in the variable names do not indicate actual directions; the names are merely a coincidence. Every coordinate is an integer with absolute value at most $50$ .

Output

For each test case, print T if the segment and the rectangle intersect, or F otherwise, one result per line. When both endpoints of the segment lie inside the rectangle, that also counts as intersecting, so print T.

Examples3

Example 1
Input
```
1
4 9 11 2 1 5 7 1
```
Expected output
```
F
```
Example 2
Input
```
1
2 2 3 3 0 0 5 5
```
Expected output
```
T
```

Example 3

Input

4
4 9 11 2 1 5 7 1
2 2 3 3 0 0 5 5
-10 0 10 0 -5 -5 5 5
6 6 10 10 0 0 5 5

Expected output

F
T
T
F