Interstellar Orders: Rectangle Intersection¶
Estimated time limit: 0.5 seconds. Memory limit: 128 MB.
On the target judge, use twice the largest per-case median runtime of the reference program, rounded up to a multiple of \(0.5\) seconds. See the reference environment.
Story¶
After completing its motion-calculation orders, the interstellar computing center is asked to prepare geometry exercises. Some rectangles are flattened into segments or even points. The center must determine whether the resulting shapes have anything in common.
Formal Problem Statement¶
Given two closed rectangles \(A,B\) in the Cartesian plane, determine whether \(A\cap B\) is nonempty. Their sides are parallel to the coordinate axes. Each rectangle is specified by two opposite corners in either order.
A rectangle includes its interior and boundary. Equal coordinates along one axis may make it a segment; equal coordinates along both axes make it a point. A single shared point counts as an intersection.
Solid outlines represent \(A\) and dashed outlines represent \(B\) . The first three pairs intersect; the fourth does not. In the second pair, the segment lies inside the rectangle.
Input¶
The first line contains \(T\) . Each of the next \(T\) lines contains eight integers:
x1 y1 x2 y2 x3 y3 x4 y4
The first four numbers specify the opposite corners of \(A\) , and the last four those of \(B\) .
Output¶
For each pair, output Intersection Found if the shapes intersect, or Intersection Not Found otherwise. Match the capitalization and spaces exactly. For \(T=0\) , the output is empty.
Samples¶
Sample 1¶
Input¶
13
0 0 1 1 2 2 3 3
-1 2 2 -1 0 0 1 1
0 0 0 0 0 0 0 0
0 1 0 5 0 2 0 3
0 0 5 5 2 -5 3 0
0 0 5 0 2 -1 2 2
0 0 2 2 -1 -1 1 1
0 0 0 0 5 0 -1 0
-1 -1 -5 -5 -5 0 -5 -2
-1 -1 -5 -5 -2 -1 -2 -2
-2 1 2 -1 1 2 -1 -2
0 0 2 2 0 1 -1 1
0 0 0 0 1 1 1 1
Output¶
Intersection Not Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Found
Intersection Not Found
Sample 2¶
Input¶
4
0 0 4 4 2 1 2 3
0 2 4 2 2 0 2 4
1 1 1 1 2 2 2 2
-1000000000 -1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Output¶
Intersection Found
Intersection Found
Intersection Not Found
Intersection Found
Sample 3¶
Input¶
0
Output¶
Sample Explanation¶
Sample 1 covers disjoint shapes, containment, coincident points, overlapping segments and boundary contact. In sample 2, the first pair is a rectangle containing a segment and the second pair consists of two segments meeting at a point; both intersect. The fourth pair shares a point at the coordinate limit.
Constraints and Guarantees¶
For 100% of the data: \(0\le T\le1000\) and \(|x_i|,|y_i|\le10^9\) for \(1\le i\le4\) . Degenerate rectangles and either order of opposite corners are allowed.
| Score | Additional conditions |
|---|---|
| 100% | None |