<|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.

496. L-Shapes
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Let's say that two line segments of non-zero length form an  if they are at a  angle to each other and one endpoint of one segment coincides with one endpoint of the other.

There are N line segments on a plane. The segments are numbered from 1 to N. Count the number of distinct pairs of segments that form L-shapes. Two pairs are considered distinct if they contain segments with different numbers.

Input
The first line of the input line contains the integer N (1 ≤ N ≤ 5000). Each of the following N lines describes one segment and contains four integers x1, y1, x2, y2 (), where (x1, y1) and (x2, y2) are endpoints of the segment. It may be assumed that for each segment x1 ≠q x2 or y1 ≠q y2.

Output
The output file should contain a single integer, the total number of distinct pairs of line segments forming L-shapes.

Example(s)
sample input
sample output
7
0 4 0 7
4 4 1 6
1 6 -3 0
4 4 0 4
0 0 0 4
0 0 0 2
0 4 4 4
5



Note. In the example the L-shapes are formed by the following pairs of segments: (1, 4), (1, 7), (2, 3), (4, 5), (5, 7). Note that the segments 4 and 7 coincide, but the pairs (1, 4) and (1, 7), for example, are still considered distinct.

<|response|>
1. Abridged Problem Statement
Given N (1 ≤ N ≤ 5000) non‐degenerate line segments on the plane, count the number of unordered pairs of segments that form an "L‐shape." Two segments form an L‐shape if
  • They share exactly one endpoint.
  • They meet at a right angle at that shared endpoint.

2. Key Observations
- Any L‐shape must occur at a shared endpoint P.
- At P, each segment contributes a direction vector (dx,dy). Two segments are perpendicular exactly when their direction vectors have dot product zero.
- Checking all O(N²) pairs is too slow for N=5000.
- Instead, group segments by each endpoint P, and at P count how many segments go in each direction.
- For each direction d at P, the perpendicular direction is computed by rotating 90°: (dx,dy)→(−dy,dx), then re-canonicalize. If at P there are c(d) segments in direction d and c(p) in direction p, they form c(d)·c(p) L‐shapes.
- Summing c(d)·c(p) over all directions d at P double‐counts each unordered pair (once as (d,p) and once as (p,d)), so we divide by 2.
- Finally, sum over all points P to get the answer.

3. Full Solution Approach
Step 1: Normalize Directions
  - For a segment from (x₁,y₁) to (x₂,y₂), compute raw vector (dx,dy)=(x₂−x₁,y₂−y₁).
  - Divide by g = gcd(|dx|,|dy|) to make it primitive.
  - Enforce a canonical orientation so that each collinear set of vectors maps to the same key:
    • If dx<0, flip both dx,dy → (−dx,−dy).
    • Else if dx==0, force dy=+1.
    • Else if dy==0, force dx=+1.
  - Result: a unique (dx,dy) for each line‐of‐sight direction.

Step 2: Build Endpoint‐to‐Direction Counts
  - Use a map from point P=(x,y) to another map that counts how many segments at P have each normalized direction d.
  - For each segment, after computing its normalized d, increment count at both endpoints P₁ and P₂.

Step 3: Count L‐Shapes at Each Point
  - For each point P, let M be the map direction→count.
  - Initialize local_sum = 0.
  - For each (d = (dx,dy), c = M[d]):
      • Compute its perpendicular by swapping dx and dy then negating dx: (dx,dy)→(−dy,dx); re-canonicalize.
      • If M contains p with count c′, add c·c′ to local_sum.
  - The unordered pairs at P are local_sum/2 (because (d,p) and (p,d) both contributed).

Step 4: Aggregate
  - Sum local_sum/2 over all points P.
  - Print the total.

Complexity:
  - Normalizing each segment: O(log max‐coord) for gcd.
  - Inserting into maps: O(log N) each.
  - Total ≈ O(N·log N). Fits within the limits.

4. C++ Implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<array<int, 4>> a;

void read() {
    cin >> n;
    a.resize(n);
    for(auto& x: a) {
        cin >> x[0] >> x[1] >> x[2] >> x[3];
    }
}

void solve() {
    // An L-shape is two segments meeting at a shared endpoint at a right angle.
    // For each segment compute its normalized direction (dx, dy) reduced by gcd
    // and canonically oriented (dx >= 0, axis directions fixed), then for each
    // of its two endpoints record that direction. slopes_per_point maps a point
    // to a multiset of directions of segments incident there. At a point, two
    // incident segments are perpendicular when their directions are negatives
    // of a 90-degree rotation; for each direction we look up its perpendicular
    // direction (rotate by 90: (dx, dy) -> (-dy, dx), then re-canonicalize) and
    // add the product of the two counts. Summing over all points double-counts
    // each pair (once per endpoint considered), so we divide by 2.

    map<pair<int, int>, map<pair<int, int>, int>> slopes_per_point;

    for(auto i = 0; i < n; i++) {
        int dx = a[i][2] - a[i][0];
        int dy = a[i][3] - a[i][1];
        int g = gcd(dx, dy);
        dx /= g;
        dy /= g;

        if(dx < 0) {
            dx = -dx;
            dy = -dy;
        }

        if(dx == 0) {
            dy = 1;
        }

        if(dy == 0) {
            dx = 1;
        }

        slopes_per_point[{a[i][0], a[i][1]}][{dx, dy}]++;
        slopes_per_point[{a[i][2], a[i][3]}][{dx, dy}]++;
    }

    int ans = 0;
    for(auto& [_, slopes]: slopes_per_point) {
        int cur = 0;
        for(auto& [slope, cnt]: slopes) {
            auto [dx, dy] = slope;
            swap(dx, dy);
            dx *= -1;
            if(dx < 0) {
                dx = -dx;
                dy = -dy;
            }

            if(slopes.count({dx, dy})) {
                cur += cnt * slopes[{dx, dy}];
            }
        }

        ans += cur;
    }

    cout << ans / 2 << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation
```python
import sys
import threading

def main():
    import math
    input = sys.stdin.readline

    n = int(input())
    segments = [tuple(map(int, input().split())) for _ in range(n)]

    # Map: point (x,y) -> dict of direction (dx,dy) -> count
    mp = {}

    def normalize(dx, dy):
        """Return a canonical primitive direction for vector (dx,dy)."""
        g = math.gcd(dx, dy)
        dx //= g
        dy //= g
        # Ensure dx >= 0, or if dx==0 then dy>0
        if dx < 0:
            dx, dy = -dx, -dy
        if dx == 0:
            # vertical line: force dy = +1
            dy = 1
        if dy == 0:
            # horizontal line: force dx = +1
            dx = 1
        return dx, dy

    # Build the mapping
    for x1, y1, x2, y2 in segments:
        dx, dy = x2 - x1, y2 - y1
        dirn = normalize(dx, dy)
        for pt in ((x1,y1), (x2,y2)):
            if pt not in mp:
                mp[pt] = {}
            mp[pt][dirn] = mp[pt].get(dirn, 0) + 1

    ans = 0
    # For each shared endpoint, count perpendicular pairs
    for slopes in mp.values():
        for (dx, dy), cnt in slopes.items():
            # perpendicular vector
            pdx, pdy = -dy, dx
            pdx, pdy = normalize(pdx, pdy)
            # add cross count if exists
            cnt2 = slopes.get((pdx, pdy), 0)
            ans += cnt * cnt2

    # Every pair was counted twice (A with B and B with A)
    print(ans // 2)

if __name__ == "__main__":
    threading.Thread(target=main).start()
```
