14CUnreviewed1700GPT-5.4 (high)

Four Segments

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

brute force constructive algorithms geometry implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

For an axis-parallel rectangle, every side is either perfectly horizontal or perfectly vertical. More importantly: how many different $x$ -coordinates and $y$ -coordinates can appear among all endpoints?

If the four segments really are the four sides of a rectangle, then the endpoint $x$ -values must be exactly $x_L$ and $x_R$ , and the endpoint $y$ -values must be exactly $y_B$ and $y_T$ . So both distinct-counts must be $2$ .

Once you know $x_L < x_R$ and $y_B < y_T$ , the rectangle is completely determined. There are only four possible side segments.

Normalize each segment so its endpoints are stored in a consistent order. Then compare the multiset of given segments with the multiset of the four expected rectangle sides.

Build the four required sides:

[(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)]

If and only if the normalized input segments match this multiset exactly, answer YES. Otherwise it is NO.

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:

read the $4$ input segments and normalize them
collect all endpoint $x$ 's and $y$ 's
if the number of distinct $x$ 's or $y$ 's is not $2$ , print NO
build the four expected rectangle sides from the two $x$ 's and two $y$ 's
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.

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

array<ll, 4> normSeg(ll x1, ll y1, ll x2, ll y2) {
    if (make_pair(x1, y1) > make_pair(x2, y2)) {
        swap(x1, x2);
        swap(y1, y2);
    }
    return {x1, y1, x2, y2};
}

int main() {
    setIO();

    multiset<array<ll, 4>> got, need;
    set<ll> xs, ys;

    for (int i = 0; i < 4; ++i) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        got.insert(normSeg(x1, y1, x2, y2));
        xs.insert(x1);
        xs.insert(x2);
        ys.insert(y1);
        ys.insert(y2);
    }

    if (xs.size() != 2 || ys.size() != 2) {
        cout << "NO\n";
        return 0;
    }

    vector<ll> vx(xs.begin(), xs.end());
    vector<ll> vy(ys.begin(), ys.end());

    ll xL = vx[0], xR = vx[1];
    ll yB = vy[0], yT = vy[1];

    need.insert(normSeg(xL, yB, xR, yB));
    need.insert(normSeg(xL, yT, xR, yT));
    need.insert(normSeg(xL, yB, xL, yT));
    need.insert(normSeg(xR, yB, xR, yT));

    cout << (got == need ? "YES\n" : "NO\n");
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

array<ll, 4> normSeg(ll x1, ll y1, ll x2, ll y2) {
    if (make_pair(x1, y1) > make_pair(x2, y2)) {
        swap(x1, x2);
        swap(y1, y2);
    }
    return {x1, y1, x2, y2};
}

int main() {
    setIO();

    multiset<array<ll, 4>> got, need;
    set<ll> xs, ys;

    for (int i = 0; i < 4; ++i) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        got.insert(normSeg(x1, y1, x2, y2));
        xs.insert(x1);
        xs.insert(x2);
        ys.insert(y1);
        ys.insert(y2);
    }

    if (xs.size() != 2 || ys.size() != 2) {
        cout << "NO\n";
        return 0;
    }

    vector<ll> vx(xs.begin(), xs.end());
    vector<ll> vy(ys.begin(), ys.end());

    ll xL = vx[0], xR = vx[1];
    ll yB = vy[0], yT = vy[1];

    need.insert(normSeg(xL, yB, xR, yB));
    need.insert(normSeg(xL, yT, xR, yT));
    need.insert(normSeg(xL, yB, xL, yT));
    need.insert(normSeg(xR, yB, xR, yT));

    cout << (got == need ? "YES\n" : "NO\n");
}

View on Codeforces Back to the list

Four Segments

Progressive nudges

Full explanation

Observation 1

Observation 2

How to compare segments

Why this is correct

If the algorithm prints `YES`

If the given segments form the required rectangle

Complexity

Generated C++

Four Segments

Progressive nudges

Full explanation

Observation 1

Observation 2

How to compare segments

Why this is correct

If the algorithm prints YES

If the given segments form the required rectangle

Complexity

Generated C++

If the algorithm prints `YES`