p493.in1
======================
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

=================
p493.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;
}

=================
p493.ans1
======================
5
4

=================
statement.txt
======================
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


=================
