Poj Solution 1925

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

#include"stdio.h"
#include"math.h"
#include"memory.h"


int x[5010],h[5010];
int pos[1000001];

int n;

void init()
{
    int i;
    scanf( "%d", &n );

    for( i=0; i<n; i++ )
        scanf( "%d %d", x+i, h+i );

    memset( pos, -1, sizeof(int)*(x[n-1]+1) );
}

void doit()
{
    int i,j,l,y,k;
    int ans;

    ans = 100000;
    pos[0] = 0;

    for( i=1; i<n; i++ )
    {
        
        l = x[i] - (int)sqrt( (double)h[i]*h[i] - (double)( h[i] - h[0] )*( h[i] - h[0] ) );

        for(j = l>0?l:0 ; j < x[i] ; j ++ )
        if(pos[j] >=0 )
        {
            y = (x[i]<<1) - j;
            k = pos[j] + 1;

            if( y >= x[n-1] )
            {
                if( k < ans ) ans = k;
            }
            else if( pos[y] < 0 || k < pos[y] ) pos[y] = k;
        }

//        if(i%100==0)
//            printf("::%dn", i);
    }

    if( ans == 100000 ) ans = -1;

    printf( "%dn", ans );
}

int main()
{
    int i,cas;

    scanf( "%d", &cas );
    for( i=1; i<=cas; i++ )
    {
        init();
        doit();
    }

    return 0;
}