Poj Solution 1727

http://poj.org/problem?id=1727

#include "stdio.h"
#include "algorithm"
using namespace std;

struct event{
    int t, x;
}p[100000];

bool cmp( event &a, event &b ) {
    return a.x+a.t < b.x+b.t;
}
int n, m;

void input( ) {
    int i;
    scanf( "%d%d", &n, &m);
    for( i=0; i<n; i++ )
        scanf( "%d%d", &p[i].t, &p[i].x );

}

bool check( int lt ) {
    int i, lx, j;
    lx = -100000000;
    for( i=0, j=0; i<n&&j<=m; i++ ) {
        if( abs( p[i].x - lx ) > p[i].t - lt ) {
            lx = p[i].x + ( p[i].t - lt );
            j++;
        }
    }
    return j<=m;
}

int main( ) {
    int i, s, a, b, j, c;
    scanf( "%d", &s );
    for( i=1; i<=s; i++ ) {
        input( );
        a = 1000000;
        b = -10000000;

        for( j=0; j<n; j++ )
            if( a > p[j].t ) a = p[j].t;

        std::sort( p, p+n, cmp );
        a++;
        while( a > b+1 ) {
            c = (a+b)/2;
            if( check( c ) )
                b = c;
            else
                a = c;
        }

        printf( "Case %d: %dn", i, b );
    }
    return 0;
}