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

```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;
};

struct building {
    int64_t l, r, h;
};

int n;
vector<int64_t> L, R, H;

void read() {
    cin >> n;
    L.assign(n, 0);
    R.assign(n, 0);
    H.assign(n, 0);
    for(int i = 0; i < n; i++) {
        cin >> L[i] >> R[i] >> H[i];
    }
}

void solve() {
    // Buildings are disjoint, so sort them by L (which also sorts them by R).
    // Each one has a left side and a right side that must be fully lit. A side
    // is fully lit exactly when its bottom corner (at height 0) is visible to
    // some lamp, because the rest of the vertical side sits above the bottom
    // and is at least as easy to see over the flat roofs in between.
    //
    // A lamp at (px, py) sees the left side of a building to its right unless a
    // roof in between cuts off the bottom. Sweeping the buildings rightward and
    // keeping the steepest "shadow" ray cast so far (the line grazing a
    // previous top-right corner) lets us mark, in one pass, every left side
    // whose bottom clears that shadow; a building at least as tall as the lamp
    // blocks everything further out and ends the sweep. Right sides are handled
    // by the mirror sweep going leftward, so a single lamp marks every side it
    // covers via two cross-product sweeps.
    //
    // The placement can be done greedily, left to right. For the left side of a
    // building the only useful vantage is the gap to its immediate left: if
    // that neighbour is shorter we light the side from the building's own
    // top-left corner, otherwise from the neighbour's top-right corner, which
    // looks straight across the empty gap.
    //
    // For an uncovered right side at (R[i], 0) the lamp must come from the
    // right, and we want it as high as possible relative to that bottom corner,
    // i.e. the future building k whose top-left corner (L[k], H[k]) makes the
    // steepest ray up from (R[i], 0). The steepest-corner choice is optimal by
    // an exchange argument. A lamp covers R[i] only if the straight segment
    // from (R[i], 0) to it grazes over every roof in between, so the segment's
    // slope must be at least the slope to each intervening top-left corner; the
    // binding constraint is exactly the steepest such corner, k. Any lamp that
    // covers R[i] therefore sits on or above the ray through (R[i], 0) and
    // (L[k], H[k]), which means k itself is the lowest, left-most, hence
    // highest angle that still sees R[i]. Among all valid lamps it has
    // the smallest slope to every later right side as well, so the set of right
    // sides any other valid lamp can reach is a subset of what k reaches:
    // committing to k never loses future coverage, and since we only ever place
    // a lamp when a side is genuinely uncovered (at most one per adjacent pair,
    // left side first), each placement is forced and maximally far-reaching,
    // which gives the minimum. Two zero-height sentinels, one just left of all
    // buildings and one just right of them, let the gap logic treat the two
    // ends uniformly: after sorting they are the first and last entries, so
    // every real side faces a defined neighbour and the rightmost right side
    // falls back to the left sentinel.

    vector<building> a(n);
    for(int i = 0; i < n; i++) {
        a[i] = {L[i], R[i], H[i]};
    }

    sort(a.begin(), a.end(), [](const building& x, const building& y) {
        return x.l < y.l;
    });

    int64_t left_x = a.front().l, 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});

    int last = (int)a.size() - 1;

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

    // p1 / q1 < p2 / q2, where each slope is a signed distance over a height.
    auto lt_slope = [](int64_t p1, int64_t q1, int64_t p2, int64_t q2) {
        return p1 * q2 < p2 * q1;
    };

    auto cover_left = [&](int64_t px, int64_t py) {
        int64_t bn = 0, bd = 1;
        for(int j = 0; j < last; j++) {
            if(a[j].r <= px) {
                continue;
            }
            if(!lt_slope(a[j].l - px, py, bn, bd)) {
                lit_left[j] = 1;
            }
            if(a[j].h >= py) {
                break;
            }
            if(lt_slope(bn, bd, a[j].r - px, py - a[j].h)) {
                bn = a[j].r - px;
                bd = py - a[j].h;
            }
        }
    };

    auto cover_right = [&](int64_t px, int64_t py) {
        int64_t bn = 0, bd = 1;
        for(int j = last - 1; j >= 1; j--) {
            if(a[j].l >= px) {
                continue;
            }
            if(!lt_slope(px - a[j].r, py, bn, bd)) {
                lit_right[j] = 1;
            }
            if(a[j].h >= py) {
                break;
            }
            if(lt_slope(bn, bd, px - a[j].l, py - a[j].h)) {
                bn = px - a[j].l;
                bd = py - a[j].h;
            }
        }
    };

    int ans = 0;
    auto place = [&](int64_t px, int64_t py) {
        ans++;
        cover_left(px, py);
        cover_right(px, py);
    };

    for(int i = 0; i < last; i++) {
        if(!lit_left[i + 1]) {
            if(a[i].h < a[i + 1].h) {
                place(a[i + 1].l, a[i + 1].h);
            } else {
                place(a[i].r, a[i].h);
            }

            continue;
        }

        if(!lit_right[i]) {
            int best = 0;
            int64_t bn = 1, bd = 0;
            for(int j = i + 1; j < last; j++) {
                if(!lt_slope(bn, bd, a[j].l - a[i].r, a[j].h)) {
                    best = j;
                    bn = a[j].l - a[i].r;
                    bd = a[j].h;
                }
            }

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

    cout << ans << '\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();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation

```python
import sys


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

    We compare by cross multiplication instead of division to avoid
    floating-point precision issues.

    This also works for the artificial infinity 1/0 used in the greedy search.
    """
    return p1 * q2 < p2 * q1


def solve_case(buildings):
    """
    Solve one test case.

    buildings is a list of triples (L, R, H).
    """

    # Sort buildings from left to right.
    # Since buildings do not touch or overlap, this is their geometric order.
    buildings.sort(key=lambda x: x[0])

    # Coordinates of the outermost real buildings.
    left_x = buildings[0][0]
    right_x = buildings[-1][1]

    # Add zero-height sentinel buildings on both ends.
    # Real buildings become indices 1..last-1.
    a = [(left_x - 2, left_x - 1, 0)] + buildings + [(right_x + 1, right_x + 2, 0)]

    # Index of right sentinel.
    last = len(a) - 1

    # lit_left[i] says whether the left side of building i is illuminated.
    lit_left = [False] * (last + 1)

    # lit_right[i] says whether the right side of building i is illuminated.
    lit_right = [False] * (last + 1)

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

        We sweep buildings to the right and maintain the strongest shadow ray.
        """

        # Current strongest blocking ray, represented as bn / bd.
        bn, bd = 0, 1

        # Sweep left to right.
        # The right sentinel's left side is irrelevant, so j < last.
        for j in range(last):
            l, r, h = a[j]

            # If this building is not to the right of the lamp, skip it.
            if r <= px:
                continue

            # The ray to the bottom of this left side has ratio:
            # (l - px) / py.
            # It is visible if it is not below the current blocker.
            if not lt_slope(l - px, py, bn, bd):
                lit_left[j] = True

            # A building at least as high as the lamp blocks all farther targets.
            if h >= py:
                break

            # Update blocking ray using this building's top-right corner.
            # Its ratio is (r - px) / (py - h).
            if lt_slope(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).

        This is the mirror version of cover_left.
        """

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

        # Sweep right to left over real buildings.
        for j in range(last - 1, 0, -1):
            l, r, h = a[j]

            # If this building is not to the left of the lamp, skip it.
            if l >= px:
                continue

            # The ray to the bottom of this right side has ratio:
            # (px - r) / py.
            # It is visible if it is not below the current blocker.
            if not lt_slope(px - r, py, bn, bd):
                lit_right[j] = True

            # A building at least as high as the lamp blocks all farther targets.
            if h >= py:
                break

            # Update blocking ray using this building's top-left corner.
            # Its ratio is (px - l) / (py - h).
            if lt_slope(bn, bd, px - l, py - h):
                bn, bd = px - l, py - h

    # Number of placed lamps.
    ans = 0

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

        # Count this lamp.
        ans += 1

        # Update illuminated left and right sides.
        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 i in range(last):
        # If the left side of the next building is still unlit,
        # we must place a lamp now.
        if not lit_left[i + 1]:
            # If the current building is shorter, place lamp at the next
            # building's top-left corner.
            if a[i][2] < a[i + 1][2]:
                place(a[i + 1][0], a[i + 1][2])
            else:
                # Otherwise place lamp at current building's top-right corner.
                place(a[i][1], a[i][2])

            # Continue to the next gap.
            continue

        # Otherwise, if the right side of the current building is unlit,
        # we need a lamp somewhere to the right.
        if not lit_right[i]:
            # best is the future building whose top-left corner gives
            # the steepest angle from the bottom-right corner of building i.
            best = 0

            # Current best reciprocal slope distance / height.
            # Initialize as infinity.
            bn, bd = 1, 0

            # Check all future real buildings.
            for j in range(i + 1, last):
                # Distance from right side of building i to left side of j.
                dist = a[j][0] - a[i][1]

                # Height of building j.
                height = a[j][2]

                # We want maximum height / dist,
                # equivalently minimum dist / height.
                if not lt_slope(bn, bd, dist, height):
                    best = j
                    bn, bd = dist, height

            # Place lamp at the chosen top-left corner.
            place(a[best][0], a[best][2])

    # Return minimum number of lamps.
    return ans


def main():
    # Read all integers from input.
    data = list(map(int, sys.stdin.buffer.read().split()))

    # Pointer into input array.
    idx = 0

    # Number of test cases.
    t = data[idx]
    idx += 1

    # Store answers as strings.
    out = []

    # Process each test case.
    for _ in range(t):
        # Number of buildings.
        n = data[idx]
        idx += 1

        # Read buildings.
        buildings = []
        for _ in range(n):
            l = data[idx]
            r = data[idx + 1]
            h = data[idx + 2]
            idx += 3
            buildings.append((l, r, h))

        # Solve and store answer.
        out.append(str(solve_case(buildings)))

    # Print all answers.
    sys.stdout.write("\n".join(out))


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