Under construction

Still being built. Things may change

Intersection Points

Interview

Time limit1sMemory limit256 MB

Summary
Given an axis-aligned rectangle and a segment per test case, count their shared boundary points, printing 4 for infinite overlap.
Level

Medium4 of 10

Topics
Geometry, Implementation
Solved
No attempts yet

Problem

For an axis-aligned rectangle and a line segment, count how many points lie on both the rectangle boundary and the segment. Print 4 when the segment overlaps the boundary and there are infinitely many intersection points.

Input

The first line contains TT. Each test case gives a rectangle by (xmin,ymin)(x_{min}, y_{min}) and (xmax,ymax)(x_{max}, y_{max}), then a segment from (x1,y1)(x_1,y_1) to (x2,y2)(x_2,y_2).

Output

For each test case, print the finite intersection count, or 4 when the intersections are infinite.

Examples1

  1. Example 1

    Input
    16
0 0 8 4
2 6 -2 3
0 0 8 4
0 4 9 4
0 0 8 4
3 5 6 6
0 0 8 4
-2 5 10 -1
0 0 8 4
0 5 8 5
0 0 8 4
4 3 4 1
0 0 8 4
-2 3 2 5
0 0 8 4
2 4 6 4
0 0 8 4
0 4 4 7
0 0 8 4
4 2 4 4
0 0 8 4
4 2 8 4
0 0 8 4
0 2 3 4
0 0 8 4
-4 0 12 4
0 0 8 4
4 8 4 -1
0 0 8 4
0 -2 0 6
0 0 8 4
3 4 10 4
    Expected output
    0
4
0
2
0
0
1
4
1
1
1
2
2
2
4
4