Expert.
Put your skills to the test.

Problem summary

Keep the first and last towers and as few other guarded towers as possible. Consecutive guarded towers must be at most K kilometres apart, and every intervening tower must lie strictly below the segment joining their tops. Coordinates are given in increasing order.

Constraints

N < 15000; L < 30000; K < 200; 1 ≤ Hi < 300; distinct positive integer Xi; every adjacent gap is at most K.

Worked example

Official statement sample.

8 9
1 3
2 7
5 8
6 2
9 10
12 20
13 18
15 16

5

Solution analysis

1. For each left tower i scan possible right towers j while Xj−Xi≤K. Tower j is visible precisely when its slope from i is strictly greater than the slopes of all intervening towers. Maintain the maximum previous slope as a rational numerator and denominator.
2. Whenever j is visible, relax dp[j] with dp[i]+1. Here dp[i] is the smallest number of guards needed through i, including the compulsory first tower. All edges lead to larger indices, so processing i in order is a shortest-path dynamic program.
3. In the sample, keep towers at x=1,2,9,12,15. Each consecutive distance is at most 9. In particular, the line from (2,7) to (9,10) passes above the tops at x=5 and x=6; the last segment also passes above the tower at x=13. This gives the optimal five guards.

Why it works

For fixed i, a segment to j passes strictly above every intervening top exactly when its slope exceeds their maximum slope. Thus the scan constructs exactly the legal successor edges. Every admissible guard arrangement is a path from the first to last tower, and the DAG recurrence computes the minimum number of vertices on such a path.

Watch out. Collinear intervening towers block visibility. Compare signed slopes by cross multiplication, not floating point.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>x(n),h(n),dp(n,n+1);
    for(int i=0;i<n;++i){
        cin>>x[i]>>h[i];
    }
    dp[0]=1;
    for(int i=0;i<n;++i){
        int bestNumerator=0;
        int bestDenominator=1;
        bool haveSlope=false;
        // A visible endpoint sets a new strict maximum slope from tower i.
        for(int j=i+1;j<n&&x[j]-x[i]<=k;++j){
            int numerator=h[j]-h[i];
            int denominator=x[j]-x[i];
            if(!haveSlope||numerator*bestDenominator>bestNumerator*denominator){
                dp[j]=min(dp[j],dp[i]+1);
                bestNumerator=numerator;
                bestDenominator=denominator;
                haveSlope=true;
            }
        }
    }
    cout<<dp[n-1]<<'\n';
}