Učiteljica Danka je odlučila da svoje đake odvede na klizanje. Međutim, pošto je jedino ona bila raspoložena za takvu avanturu, i đaci ostalih razreda su odlučili da se pridruže. I tako je ona sa n učenika otišla na obližnje klizalište. Kada su došli, ona je zamolila svakog đaka da joj kaže odakle će početi da se kliza, i u kom pravcu će se klizati. Kako je Danka veoma pametna učiteljica, ona je na osnovu godina svakog đaka i njihove snage i osobina zaključila i kojom brzinom će se svako klizati. Pošto veoma dugo radi kao učiteljica, ima dovoljno iskustva da sve đake može da kontroliše čak i ako se ne pomera (tj. sve vreme stoji na samo jednom mestu). Danka slabo vidi, a bezbednost dece je na prvom mestu, pa je odlučila da ponese naočare. Ali ne bilo kakve naočare, već specijalne naočare na kojima može da se namesti koliko daleko se vidi s njima (a može videti i levo i desno od svoje pozicije onoliko daleko koliko je podesila). Da bi bila sigurna da je sve u redu, odlučila je da podesi daljinu naočara tako da bar u jednom momentu vidi bar k učenika. Pošto ste Vi njen najbolji učenik, zamolila vas je da joj izračunate kolika je najmanja moguća daljina na koju treba da podesi naočare i gde treba da stoji tako da to važi.

Klizalište je predstavljeno jednom beskonačnom pravom, pozicije učiteljice i đaka predstavljene su x-koordinatom na toj pravoj.

Ulaz.

(Ulazni podaci se nalaze u datoteci klizanje.in) U prvom redu datoteke se nalaze brojevi n ( 4 ≤ n ≤ 1000) i k (1 ≤ k ≤ n). U svakom od narednih n redova se nalaze 2 broja: prvi broj x[i] (0 ≤ x[i] ≤ 500.000) označava početnu poziciju đaka, a drugi broj v[i] (-1000 ≤ v[i] ≤ 1000) brzinu đaka (odnosno koliko će se pomeriti svake sekunde, ako je brzina negativna, to znači da se kreće ulevo po x osi). Dva ili više učenika mogu imati istu početnu poziciju, ali u tom slučaju ne mogu imati jednake brzine.

Napomena.

Đaci ne menjaju brzinu tokom spuštanja, i nijedan đak neće "pregaziti" učiteljicu.

Izlaz.

(Izlazne podatke upisati u datoteku klizanje.out) U izlaznu datoteku treba ispisati traženu najmanju moguću daljinu. Dozvoljena relativna greška je 10^-8. Ako je r korektno rešenje, a s rešenje koje proizvede vaš program onda treba da važi:
2|r-s| / (|r|+|s|) ≤ 10^-8

Primer 1.

4 3
0 1
2 4
5 -2
7 0

1.5

Objašnjenje.

U trenutku 0.5, poslednja tri klizača će biti na pozicijama 4, 4, 7, redom pa će Danka, ako stoji na poziciji 5.5 i podesi daljinu na 1.5, videti njih trojicu.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int TEST = 0;

const int MAXN = 10000;
const int MAXP = MAXN * MAXN;

typedef struct {
   int x;
   int v;
} Djak;


typedef struct {
   int dx;
   int dv;
   int i;
   int j;
} Presek;

Djak djaci[MAXN];
Presek preseci[MAXP];
int poz[MAXN];
int koji[MAXN];



inline double abs (double a)
{
 return a>=0?a:-a;
}
inline double min(double a, double b) {
 return a<b?a:b;
}
inline int min(int a, int b) {
 return a<b?a:b;
}
inline int max(int a, int b) {
 return a>b?a:b;
}

int presek(Djak* a, int i, int j, Presek& p) {
     p.dx = a[i].x - a[j].x;
     p.dv = a[j].v - a[i].v;
     p.i = i;
     p.j = j;
     return p.dx * p.dv > 0;
}

int op(const void * a, const void * b) {
    Djak* pa = (Djak *)a;
    Djak* pb = (Djak *)b;
    if (pa->x != pb->x)
       return (pa->x) - (pb->x);
    return (pa->v) - (pb->v);
}

int cmpPresek(const void * a, const void * b) {
    Presek* pa = (Presek *)a;
    Presek* pb = (Presek *)b;
    int v =  pa->dx * pb->dv - pb->dx * pa->dv;
    if (v!=0)
       return v;
    
    int r = djaci[pa->i].x - djaci[pb->i].x;
    if (r!=0) return r;
    r = djaci[pa->j].x - djaci[pb->j].x;
    if (r!=0) return r;
    r = pa->i - pb->i;    
    if (r!=0) return r;
    r = pa->j - pb->j;
    return r;
}

void razmeni(int* poz, int* koji, int i, int j)
{
     koji[poz[i]]=j;
     koji[poz[j]]=i;
     int pom = poz[i];
     poz[i] = poz[j];
     poz[j] = pom;     
}

double vreme(Presek& p) {
       return 1.0*p.dx/p.dv;
}

double pozicija(Djak& a, double t) {
       return (t*a.v+a.x);     
}

double rastojanje(Djak* a, int i, int j, Presek& p) {
       double t= vreme(p);
       return abs(pozicija(a[i],t)-pozicija(a[j],t));
}



double calc(int n, int k, Djak* a) {
    qsort(a, n, sizeof(Djak), op);

    int broj = 0;
    int i,j;
    double res = 1e50;
    for (i=0;i<n;i++) {
        if (i+k-1 < n)
           res = min(res, (double)abs(a[i].x - a[i+k-1].x));
        if (TEST)
           printf("%d %d\n", a[i].x, a[i].v);
        if (i+1<n) 
           if (a[i].x==a[i+1].x && a[i].v==a[i+1].v)
              printf("imamo istih %d %d\n", a[i].x, a[i].v);
        poz[i] = i;
        koji[i] = i;
    }
    if (TEST)
       printf("\n");

    for (i = 0;i<n;i++) 
        for(j = i+1;j<n;j++)
        {
            if (presek(a, i, j, preseci[broj])>0)
               broj++;
        }
    int start = clock();
  
    qsort(preseci, broj, sizeof(Presek), cmpPresek);
      
     
    printf("sortiranje %d %d\n", broj, clock()-start);  
      
   
    int p;
    for (p = 0;p<broj;p++) {
        i = preseci[p].i;
        j = preseci[p].j;
        int c;
        if (TEST) {
           for (c=0;c<n;c++) 
               printf("%d  ", koji[c]);
           printf("\n");
           printf("%d %d\t%d %d\n", i, j, poz[i], poz[j]);
        }

        if (koji[poz[i]]!=i || koji[poz[j]]!=j)
           printf("GREEESKA %d %d\n", poz[i], poz[j]);

        if (abs(poz[i]-poz[j])>1) {
           printf("BAAAD %d %d\n", poz[i], poz[j]);
        }
        razmeni(poz, koji, i, j);
        int left = min(poz[i], poz[j]);
        int right = left + k-1;
        double r ;
        if (right <n)
        {
           r = rastojanje(a, koji[left], koji[right], preseci[p]);        
           if (TEST) 
              printf("\t%d %d %lf\n", left , right, r);
           res = min(res, r); 
        }
        right = max(poz[i], poz[j]);
        left = right - k+1;
        if (left>=0)
        {
           r =  rastojanje(a, koji[left], koji[right], preseci[p]);        
           if (TEST)
              printf("\t%d %d %lf\n", left , right, r);
           res = min(res, r); 
        }
    }    
    return res;
}


int main() {
    FILE* fin = fopen("klizanje.in", "r");
    FILE* fout = fopen("klizanje.out", "w");
    
    
    int n,k;
    fscanf(fin, "%d%d", &n, &k);
    int i;
    for(i = 0;i<n;i++)
       fscanf(fin, "%d%d", &(djaci[i].x), &(djaci[i].v));
    
    double res = calc(n, k, djaci);
    
    fprintf(fout, "%lf\n", res);
    fclose(fin);
    fclose(fout);
    
    system("pause");
    return 0;
}