Four Segments

Observation 1

If four segments form a rectangle with sides parallel to the axes, then all rectangle corners are determined by just two $x$-values and two $y$-values:

• left and right: $x_L < x_R$
• bottom and top: $y_B < y_T$

So among all $8$ endpoints, there can be only:

• exactly $2$ distinct $x$-coordinates
• exactly $2$ distinct $y$-coordinates

If either count is not $2$, then it is impossible. End of story.

Also, having two distinct $x$'s and two distinct $y$'s already guarantees positive width and height, so the area is positive.

Observation 2

Once $x_L, x_R, y_B, y_T$ are known, the rectangle is uniquely determined. The only valid sides are:

$$[(x_L,y_B),(x_R,y_B)], [(x_L,y_T),(x_R,y_T)], [(x_L,y_B),(x_L,y_T)], [(x_R,y_B),(x_R,y_T)]$$

So the whole problem becomes:

Do the given four segments match these four segments exactly, ignoring input order and endpoint order?

That is all. No fancy geometry. No cross products. No sacrificing goats to the implementation gods.

How to compare segments

A segment may be given in either direction, so first normalize it:

• if endpoint $A$ is lexicographically larger than endpoint $B$, swap them
• store the segment as the ordered 4-tuple $(x_1,y_1,x_2,y_2)$

Now the same undirected segment always has the same representation.

Then:

1. read the $4$ input segments and normalize them
2. collect all endpoint $x$'s and $y$'s
3. if the number of distinct $x$'s or $y$'s is not $2$, print NO
4. build the four expected rectangle sides from the two $x$'s and two $y$'s
5. compare the two multisets

If they are identical, print YES, otherwise NO.

Degenerate input segments are automatically rejected, because they simply will not match any of the four positive-length sides.

Why this is correct

If the algorithm prints YES

Then the normalized input multiset is exactly equal to the multiset of the four segments listed above. Those four segments are precisely the sides of the axis-parallel rectangle with corners:

$$(x_L,y_B), (x_L,y_T), (x_R,y_B), (x_R,y_T)$$

Since $x_L < x_R$ and $y_B < y_T$, this rectangle has positive area. So the given segments do form the required rectangle.

If the given segments form the required rectangle

Then all endpoints must lie on the rectangle corners, so there are exactly two distinct $x$-values and exactly two distinct $y$-values.

Moreover, the four given segments must be exactly the four sides of that rectangle. After normalizing endpoint order, the multiset of input segments is identical to the multiset of expected sides. Therefore the algorithm prints YES.

So the condition is both necessary and sufficient. Nice, tight, no bullshit.

Complexity

There are only $4$ segments, so the running time is effectively constant:

$$O(1)$$

If you want to sound extra ceremonial, you can say the set operations are $O(4 \log 4)$, which is the same thing wearing a fake mustache.