<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

532. Building Foundation
Time limit per test: 1.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

A new office building is to appear in Berland soon. Its construction has just been started, and the first problem builders are facing is to lay the foundation.

The ground at construction site area has already been hardened along n segments. Each segment is given by integer coordinates of its endpoints in the site area coordinate system. Every segment has a positive length and is parallel to either Ox axis or Oy axis. It's important to note that the ground hardening was done in such a way that only perpendicular segments could possibly have common points.

The decision has been made for the foundation to have a rectangular form. The rectangle must have the following properties:
it should have a positive area,
its sides should be parallel to one of the coordinate axes,
its sides should be situated on the hardened ground, i.e. each point of its perimeter should belong to at least one segment out of the n hardened ones.


You are to help estimating the difficulty of choosing such a rectangle. Write a program that finds the number of rectangles that can possibly be used as a foundation.

Input
The first line contains integer n (1 ≤ n ≤ 600) — the number of hardened segments. Each of the following n lines contains four space-separated integers x1, y1, x2, y2 (-109 ≤ x1,y1,x2,y2 ≤ 109) — coordinates of the segments' endpoints. Each segment has positive length and is parallel to either Ox axis or Oy axis. No two horizontal segments have a common point. No two vertical segments have a common point.

Output
Print a single integer — the number of rectangles that can possibly be used as a foundation.

Example(s)
sample input
sample output
4
0 0 1 0
0 0 0 1
1 1 1 -1
1 1 0 1
1

sample input
sample output
8
1 0 4 0
2 1 2 0
0 0 0 3
2 2 2 3
3 3 3 -1
0 3 4 3
4 1 -1 1
3 2 -1 2
6

<|response|>
## 1) Abridged problem statement

You are given **n ≤ 600** axis-aligned segments with integer endpoints.  
Each segment is either **horizontal** or **vertical**, has positive length, and:

- no two **horizontal** segments share any point,
- no two **vertical** segments share any point,

so intersections can only happen between a horizontal and a vertical segment.

Count how many **axis-aligned rectangles with positive area** can be formed such that **every point of the rectangle perimeter** lies on the union of the given segments (i.e., each side is fully covered by hardened ground).

---

## 2) Key observations

1. **A rectangle side cannot be “stitched” from multiple segments.**  
   Because no two horizontal segments touch/intersect each other, a full horizontal side of the rectangle must lie on **one** horizontal segment. Similarly, each vertical side must lie on **one** vertical segment.

2. A rectangle is defined by:
   - two horizontal segments (top and bottom),
   - and two vertical segments (left and right),
   such that each vertical segment intersects **both** chosen horizontals.

3. Fix two horizontal segments \(H_i, H_j\).  
   A vertical segment at x = \(x_v\) intersects both iff:
   - \(x_v\) lies in the **x-overlap** of the two horizontals,
   - and the vertical segment’s y-range covers both horizontal y’s.

4. If for a fixed pair of horizontals there are **cnt** vertical segments that intersect both, then the number of rectangles from this pair is:
\[
\binom{cnt}{2} = \frac{cnt(cnt-1)}{2}
\]
(choose any two such verticals as left/right sides; disjointness guarantees distinct x’s, hence positive width).

---

## 3) Full solution approach

### Step A: Normalize and split segments
Convert each input segment into one of two normalized forms:

- Horizontal: `(y, xL, xR)` with `xL < xR`
- Vertical: `(x, yL, yR)` with `yL < yR`

Store them in two arrays `H[]` and `V[]`.

### Step B: Enumerate pairs of horizontal segments
For every pair `(H[i], H[j])` with `i < j`:

- Let `H[i] = (y1, a1, b1)`, `H[j] = (y2, a2, b2)`.
- Compute overlap in x:
  - `L = max(a1, a2)`
  - `R = min(b1, b2)`
- If `L >= R`, then no rectangle is possible with these two horizontals (no positive-width overlap).

Let:
- `yLow = min(y1, y2)`
- `yHigh = max(y1, y2)`

### Step C: Count verticals intersecting both horizontals
Initialize `cnt = 0`. For each vertical `V[k] = (x, c, d)`:

It can serve as a rectangle side iff:
- `L <= x <= R`  (it hits both horizontals in x)
- `c <= yLow` and `d >= yHigh` (it spans between the two y-levels)

Increment `cnt` for each such vertical.

Add `cnt*(cnt-1)/2` to the answer.

### Complexity
Let `H = #horizontals`, `V = #verticals`, `H + V = n ≤ 600`.

- Horizontal pairs: `O(H^2)`
- For each pair scan all verticals: `O(V)`

Total: `O(H^2 * V) ⊆ O(n^3)` which is acceptable for `n=600`.

---

## 4) C++ implementation (detailed comments)

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

/*
  Building Foundation (p532 / CF 532-like)
  Count rectangles whose perimeter is fully covered by given disjoint
  horizontal/vertical segments.

  Algorithm:
    - Split segments into horizontals (y, xL, xR) and verticals (x, yL, yR).
    - For each pair of horizontals, compute x-overlap [L, R].
    - Count vertical segments with x in [L, R] and y-range covering both y's.
    - Add C(cnt, 2).
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // Use long long for coordinates safety (up to 1e9) and computations.
    struct HSeg { long long y, xL, xR; };
    struct VSeg { long long x, yL, yR; };

    vector<HSeg> H;
    vector<VSeg> V;

    for (int i = 0; i < n; i++) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (y1 == y2) {
            // Horizontal: normalize x1 <= x2
            if (x1 > x2) swap(x1, x2);
            H.push_back({y1, x1, x2});
        } else {
            // Vertical: normalize y1 <= y2
            if (y1 > y2) swap(y1, y2);
            // For axis-aligned input, x1 == x2 for vertical segments.
            V.push_back({x1, y1, y2});
        }
    }

    long long ans = 0;

    // Enumerate all pairs of horizontal segments
    for (int i = 0; i < (int)H.size(); i++) {
        for (int j = i + 1; j < (int)H.size(); j++) {
            long long y1 = H[i].y, a1 = H[i].xL, b1 = H[i].xR;
            long long y2 = H[j].y, a2 = H[j].xL, b2 = H[j].xR;

            // x-overlap interval where a vertical could intersect both
            long long L = max(a1, a2);
            long long R = min(b1, b2);

            // Need positive width possibility; if no overlap, skip
            if (L >= R) continue;

            long long yLow = min(y1, y2);
            long long yHigh = max(y1, y2);

            int cnt = 0;
            // Count vertical segments that intersect both horizontals
            for (const auto &vs : V) {
                // x must be inside overlap, and vertical must cover both y-levels
                if (vs.x >= L && vs.x <= R && vs.yL <= yLow && vs.yR >= yHigh) {
                    cnt++;
                }
            }

            // Choose any 2 of these verticals as left/right sides
            ans += 1LL * cnt * (cnt - 1) / 2;
        }
    }

    cout << ans << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))

    # horizontals: (y, xL, xR)
    # verticals:   (x, yL, yR)
    H = []
    V = []

    for _ in range(n):
        x1 = int(next(it)); y1 = int(next(it))
        x2 = int(next(it)); y2 = int(next(it))

        if y1 == y2:
            # Horizontal: normalize x1 <= x2
            if x1 > x2:
                x1, x2 = x2, x1
            H.append((y1, x1, x2))
        else:
            # Vertical: normalize y1 <= y2
            if y1 > y2:
                y1, y2 = y2, y1
            V.append((x1, y1, y2))

    ans = 0
    Hn = len(H)

    # Enumerate all pairs of horizontal segments
    for i in range(Hn):
        y1, a1, b1 = H[i]
        for j in range(i + 1, Hn):
            y2, a2, b2 = H[j]

            # Overlap of x-intervals
            L = max(a1, a2)
            R = min(b1, b2)

            # Need positive width possibility
            if L >= R:
                continue

            y_low = y1 if y1 < y2 else y2
            y_high = y2 if y1 < y2 else y1

            cnt = 0
            # Count vertical segments that intersect both horizontals
            for x, yl, yr in V:
                if L <= x <= R and yl <= y_low and yr >= y_high:
                    cnt += 1

            # Add combinations of picking 2 verticals
            ans += cnt * (cnt - 1) // 2

    sys.stdout.write(str(ans))

if __name__ == "__main__":
    solve()
```

