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

493. Illumination of Buildings
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



The city of Harbin is famous for the nighttime illumination of its buildings. Unfortunately, the economic crisis of the world has not left the welfare of the city undisturbed. An audit performed by the city council has revealed that lighting is the single largest expense in the budget of the city. Accordingly, it was decided to cut the costs for lightning as much as possible, but without sacrificing the quality of the illumination, as the council has no desire to damage the world fame of the city.

Let's consider a 2-dimensional model of the city where each building is described by three integers L, R, H and modeled as a rectangle with edges parallel to the coordinate axes and two opposing corners at the points (L, 0) and (R, H). It may be assumed that the rectangles in the model do not intersect and even do not touch each other. Line segments  and  are called the side edges and line segment  the top edge.

The city council plans to install a number of light sources to illuminate the buildings. Each light source is to be installed on a top edge of a building (possibly on an endpoint of the top edge). There may be any number of light sources on one building. It is known that a light source installed at (x1, y1) will illuminate all points (x2, y2) where the line segment  does not contain any internal points of any buildings. It is allowed for the segment to contain any (even infinite) number of edge and corner points of buildings.




The figure above shows a light source and all points illuminated by it.

You are asked to install the minimal number of light sources to ensure that both sides of each building are completely illuminated. A side of a building is completely illuminated if for every point P on the side (including endpoints) there exists at least one light source L that illuminates the point P.

Input
The input file contains several test cases. The first line of the file contains T (), the number of test cases. The line is followed by T blocks, each describing a test case.

The first line of a block contains N (1 ≤ N ≤ 1000), the number of buildings in the city. Each of the following N lines describes one building and contains three integers L, R and H (, ).

It may be assumed that the sum of squares of values of N over all test cases in an input file does not exceed .

Output
The output file should contain one line for each test case given in the input file. Each line should contain a single integer, the minimal number of light sources required to illuminate both side edges of all the buildings in the city.

Example(s)
sample input
sample output
2
4
3 4 1
5 6 1
7 8 1
1 2 10
6
3 4 1
5 6 1
7 8 1
1 2 10
11 12 10
9 10 1
5
4

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

We are given `N` disjoint, non-touching rectangular buildings. Building `i` occupies:

```text
[L_i, R_i] × [0, H_i]
```

A light source may be placed only on the top edge of a building. A point is illuminated if the segment from the light to that point does not pass through the interior of any building; touching edges/corners is allowed.

We need the minimum number of light sources so that both vertical side edges of every building are completely illuminated.

---

## 2. Key observations

### Observation 1: It is enough to illuminate bottom corners

For a vertical side, if its bottom endpoint is visible from some lamp, then every higher point on that side is also visible from that lamp.

Why? For a fixed lamp and a fixed side, the segment to a higher point lies above the segment to the bottom point. If the lower segment does not pass through any building interior, the higher one cannot be blocked either.

So each building contributes only two required points:

```text
(L_i, 0)  left side bottom
(R_i, 0)  right side bottom
```

---

### Observation 2: Sort buildings left to right

Buildings do not overlap or touch, so after sorting by `L`, their order by `R` is also fixed.

We add two artificial zero-height buildings:

- one before the leftmost building,
- one after the rightmost building.

This makes the greedy processing of boundary buildings uniform.

---

### Observation 3: Visibility from one lamp can be computed by a sweep

Consider a lamp at `(px, py)`.

To find which left sides to the right are visible, sweep buildings from left to right.

While sweeping, maintain the strongest blocking ray caused by previous buildings. For a building with top-right corner `(R, H)`, if `H < py`, then it may block farther targets. The blocking condition can be represented by the ratio:

```text
(R - px) / (py - H)
```

A target left-bottom corner `(L, 0)` is visible if:

```text
(L - px) / py >= current_blocking_ratio
```

We compare fractions by cross multiplication to avoid floating-point precision errors.

The same idea, mirrored, computes visible right sides to the left of the lamp.

---

### Observation 4: Greedy placement from left to right

Process gaps between consecutive buildings from left to right.

For current neighboring buildings `i` and `i + 1`:

#### Case 1: left side of building `i + 1` is not lit

Then we must place a lamp now. A future lamp to the right cannot illuminate this left side because the building itself blocks it.

The optimal local placement is:

- if building `i` is shorter than building `i + 1`, place at the top-left corner of building `i + 1`;
- otherwise, place at the top-right corner of building `i`.

#### Case 2: left side of building `i + 1` is already lit, but right side of building `i` is not lit

Then we need a lamp somewhere to the right.

Choose the future building `k` whose top-left corner gives the steepest angle from `(R_i, 0)`, i.e. maximize:

```text
H_k / (L_k - R_i)
```

Equivalently, minimize:

```text
(L_k - R_i) / H_k
```

This choice is optimal because it is the most useful possible lamp for illuminating the current unlit right side and future right sides.

---

## 3. Full solution approach

For each test case:

1. Sort all buildings by `L`.
2. Add two sentinel buildings of height `0`.
3. Maintain two boolean arrays:
   ```text
   lit_left[i]   = whether left side of building i is lit
   lit_right[i]  = whether right side of building i is lit
   ```
4. Define a function `place(px, py)`:
   - increment answer,
   - mark all left sides visible from `(px, py)`,
   - mark all right sides visible from `(px, py)`.
5. Sweep gaps from left to right:
   - if `lit_left[i + 1]` is false, place a lamp using Case 1;
   - else if `lit_right[i]` is false, place a lamp using Case 2.
6. Output the number of placed lamps.

Complexity per test case:

```text
Sorting:      O(N log N)
Placements:   O(N)
Each update:  O(N)
Total:        O(N^2)
```

This satisfies the constraint that the sum of `N^2` over all test cases is bounded.

---

## 4. C++ implementation with detailed comments

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

struct Building {
    long long l, r, h;
};

// Return true iff p1 / q1 < p2 / q2.
// Uses __int128 to avoid overflow during cross multiplication.
bool lt_fraction(long long p1, long long q1, long long p2, long long q2) {
    return (__int128)p1 * q2 < (__int128)p2 * q1;
}

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

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<Building> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i].l >> a[i].r >> a[i].h;
        }

        // Sort buildings from left to right.
        sort(a.begin(), a.end(), [](const Building& x, const Building& y) {
            return x.l < y.l;
        });

        // Add zero-height sentinel buildings.
        long long left_x = a.front().l;
        long long right_x = a.back().r;

        a.insert(a.begin(), {left_x - 2, left_x - 1, 0});
        a.push_back({right_x + 1, right_x + 2, 0});

        // Real buildings are now indexed 1 ... last - 1.
        int last = (int)a.size() - 1;

        vector<char> lit_left(last + 1, 0);
        vector<char> lit_right(last + 1, 0);

        auto cover_left = [&](long long px, long long py) {
            /*
                Mark all left sides visible from lamp (px, py).

                Sweep buildings from left to right.

                bn / bd stores the strongest blocking ray so far.
                A target left-bottom corner is visible if its ray is not below
                this blocking ray.
            */

            long long bn = 0;
            long long bd = 1;

            for (int j = 0; j < last; j++) {
                // Building completely to the left of the lamp cannot be a
                // left-side target to the right.
                if (a[j].r <= px) {
                    continue;
                }

                // Check whether bottom of left side is visible.
                //
                // Ray to target: (a[j].l - px) / py
                // Blocking ray: bn / bd
                if (!lt_fraction(a[j].l - px, py, bn, bd)) {
                    lit_left[j] = 1;
                }

                // If this building is at least as high as the lamp,
                // it blocks all farther targets.
                if (a[j].h >= py) {
                    break;
                }

                // Update blocking ray using this building's top-right corner.
                //
                // Blocking ratio:
                // (a[j].r - px) / (py - a[j].h)
                if (lt_fraction(bn, bd, a[j].r - px, py - a[j].h)) {
                    bn = a[j].r - px;
                    bd = py - a[j].h;
                }
            }
        };

        auto cover_right = [&](long long px, long long py) {
            /*
                Mark all right sides visible from lamp (px, py).

                This is the mirror version of cover_left.
            */

            long long bn = 0;
            long long bd = 1;

            for (int j = last - 1; j >= 1; j--) {
                // Building completely to the right of the lamp cannot be a
                // right-side target to the left.
                if (a[j].l >= px) {
                    continue;
                }

                // Ray to bottom of right side:
                // (px - a[j].r) / py
                if (!lt_fraction(px - a[j].r, py, bn, bd)) {
                    lit_right[j] = 1;
                }

                // A building at least as high as the lamp blocks all farther
                // targets in this direction.
                if (a[j].h >= py) {
                    break;
                }

                // Update blocking ray using this building's top-left corner.
                //
                // Blocking ratio:
                // (px - a[j].l) / (py - a[j].h)
                if (lt_fraction(bn, bd, px - a[j].l, py - a[j].h)) {
                    bn = px - a[j].l;
                    bd = py - a[j].h;
                }
            }
        };

        int answer = 0;

        auto place = [&](long long px, long long py) {
            /*
                Place one lamp and update all sides illuminated by it.
            */
            answer++;

            cover_left(px, py);
            cover_right(px, py);
        };

        /*
            Process gaps from left to right.

            Gap i is between building i and building i + 1.
        */
        for (int i = 0; i < last; i++) {
            // First ensure the left side of the next building is lit.
            if (!lit_left[i + 1]) {
                if (a[i].h < a[i + 1].h) {
                    // Next building is taller, use its top-left corner.
                    place(a[i + 1].l, a[i + 1].h);
                } else {
                    // Current building is at least as tall, use its top-right corner.
                    place(a[i].r, a[i].h);
                }

                continue;
            }

            // If current building's right side is not lit,
            // place a lamp on the best future building.
            if (!lit_right[i]) {
                int best = -1;

                // We minimize distance / height.
                // Start with infinity, represented by 1 / 0.
                long long best_num = 1;
                long long best_den = 0;

                for (int j = i + 1; j < last; j++) {
                    long long dist = a[j].l - a[i].r;
                    long long height = a[j].h;

                    if (!lt_fraction(best_num, best_den, dist, height)) {
                        best = j;
                        best_num = dist;
                        best_den = height;
                    }
                }

                place(a[best].l, a[best].h);
            }
        }

        cout << answer << '\n';
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def lt_fraction(p1, q1, p2, q2):
    """
    Return True iff p1 / q1 < p2 / q2.

    Python integers are arbitrary precision, so cross multiplication is safe.

    We also use q = 0 to represent infinity in one greedy comparison.
    """
    return p1 * q2 < p2 * q1


def solve_case(buildings):
    # Sort buildings from left to right.
    buildings.sort(key=lambda x: x[0])

    left_x = buildings[0][0]
    right_x = buildings[-1][1]

    # Add zero-height sentinel buildings.
    #
    # Real buildings are indexed 1 ... last - 1.
    a = [(left_x - 2, left_x - 1, 0)] + buildings + [(right_x + 1, right_x + 2, 0)]

    last = len(a) - 1

    lit_left = [False] * (last + 1)
    lit_right = [False] * (last + 1)

    def cover_left(px, py):
        """
        Mark all left sides visible from lamp (px, py).

        Sweep from left to right and maintain the strongest blocking ray.
        """

        # Current blocking ray: bn / bd.
        bn, bd = 0, 1

        for j in range(last):
            l, r, h = a[j]

            # This building is not to the right of the lamp.
            if r <= px:
                continue

            # Ray to bottom of left side:
            # (l - px) / py
            #
            # It is visible if this ratio is at least bn / bd.
            if not lt_fraction(l - px, py, bn, bd):
                lit_left[j] = True

            # Building is too tall; it blocks everything farther right.
            if h >= py:
                break

            # Update blocking ray using top-right corner.
            #
            # Blocking ratio:
            # (r - px) / (py - h)
            if lt_fraction(bn, bd, r - px, py - h):
                bn, bd = r - px, py - h

    def cover_right(px, py):
        """
        Mark all right sides visible from lamp (px, py).

        Mirror version of cover_left.
        """

        # Current blocking ray.
        bn, bd = 0, 1

        for j in range(last - 1, 0, -1):
            l, r, h = a[j]

            # This building is not to the left of the lamp.
            if l >= px:
                continue

            # Ray to bottom of right side:
            # (px - r) / py
            if not lt_fraction(px - r, py, bn, bd):
                lit_right[j] = True

            # Building is too tall; it blocks everything farther left.
            if h >= py:
                break

            # Update blocking ray using top-left corner.
            #
            # Blocking ratio:
            # (px - l) / (py - h)
            if lt_fraction(bn, bd, px - l, py - h):
                bn, bd = px - l, py - h

    answer = 0

    def place(px, py):
        """
        Place one lamp and update all sides it illuminates.
        """
        nonlocal answer

        answer += 1

        cover_left(px, py)
        cover_right(px, py)

    # Process gaps from left to right.
    for i in range(last):
        # If the next building's left side is unlit, we must handle it now.
        if not lit_left[i + 1]:
            if a[i][2] < a[i + 1][2]:
                # Next building is taller.
                # Place at its top-left corner.
                place(a[i + 1][0], a[i + 1][2])
            else:
                # Current building is at least as tall.
                # Place at its top-right corner.
                place(a[i][1], a[i][2])

            continue

        # If current building's right side is unlit,
        # choose the future top-left corner with maximum height / distance.
        if not lit_right[i]:
            best = -1

            # Current best reciprocal slope: distance / height.
            # Infinity is represented as 1 / 0.
            best_num, best_den = 1, 0

            for j in range(i + 1, last):
                dist = a[j][0] - a[i][1]
                height = a[j][2]

                # We minimize dist / height.
                if not lt_fraction(best_num, best_den, dist, height):
                    best = j
                    best_num, best_den = dist, height

            place(a[best][0], a[best][2])

    return answer


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    idx = 0

    t = data[idx]
    idx += 1

    answers = []

    for _ in range(t):
        n = data[idx]
        idx += 1

        buildings = []

        for _ in range(n):
            l = data[idx]
            r = data[idx + 1]
            h = data[idx + 2]
            idx += 3

            buildings.append((l, r, h))

        answers.append(str(solve_case(buildings)))

    sys.stdout.write("\n".join(answers))


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