LA3548 Fortune at El Dorado ( two pointer )

/*
    Problem : http://poj.org/problem?id=2899
    Problem : https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=219&page=show_problem&problem=1549

    !!! I couldn't find this solution complexity but I think this is not a good solution !!!
    !!! Try SegmentTree instead : http://pastebin.com/cfQbV1mA
*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;
#define lli long long int

int x[1005] , y[1005];

int main()
{

    int T; scanf( "%d" , &T );
    while ( T-- )
    {
        int n , m;
        scanf( "%d %d" , &n , &m );
        int minX = 1005 , maxX = 0;
        int minY = 1005 , maxY = 0;
        for ( int i=0 ; i<n ; i++ )
        {
            scanf( "%d %d" , &y[i] , &x[i] );
            // y[i] = i+1 , x[i] = i+1;
            minY = min( minY , y[i] );
            maxY = max( maxY , y[i] );
            minX = min( minX , x[i] );
            maxX = max( maxX , x[i] );
        }

        if ( (n == 0) || (m == 0) )
        {
            printf( "0\n" );
            continue;
        }

        int ans = 0;
        {
            vector< pair<int,int> > v;
            for ( int i=0 ; i<n ; i++ ) v.push_back( make_pair( y[i] , x[i] ) );
            sort( v.begin() , v.end() );

            int S = min( maxY-minY+1 , m );
            for ( int h=1 ; h<=S ; h++ )        // set fixed width and height and walk on columns
            {
                if ( (m/h) == (m/(h+1)) ) continue;     // simple and nice optimization !!!
                int w = m / h;

                multiset<int> st;
                for ( int i1=0,i2=0 ; i2<n ; i2++ )
                {
                    st.insert( v[i2].second );
                    while ( (v[i2].first - v[i1].first) > h )
                    {
                        st.erase( st.find( v[i1].second ) );
                        i1++;
                    }

                    int cnt = 0;
                    for ( multiset<int>::iterator si=st.begin(),sj=st.begin() ; sj!=st.end() ; sj++ )
                    {
                        cnt++;
                        while ( (*sj - *si) > w ) cnt-- , si++;
                        ans = max( ans , cnt );
                    }
                }
            }
        }

        cout<<ans<<"\n";
    }

    return 0;
}