Dve grupe krtica su se našle na susednim stranicama pravougaone livade oivičene ogradom. Svaka krtica je pronašla po jednu rupu na ogradi. U trenutku kad je počela da pada kiša krtice su počele da kopaju tunele u pravcu normalnom na ogradu. Krtica kopa tunel dok ne dođe na već iskopan tunel (svi tuneli su na istoj dubini), a onda prestaje i počinje da se kreće već iskopanim tunelom. Ako je data brzina kojom svaka krtica kopa tunel, izračunati koliko dugo će svaka krtica kopati tunel pre nego što naiđe na već iskopan tunel. Ako neka krtica nikada neće naići na iskopan tunel, ispisati -1.

Ulaz:

(Ulazni podaci se nalaze u datoteci krtice.in) U prvom redu datoteke nalaze se dva cela broja: n₁ - broj krtica u prvoj grupi (one koje se nalaze na jednoj strani livade) i n₂ - broj krtica u drugoj grupi (krtice koje se nalaze na drugoj strani livade) (0 < n₁, n₂ < 5000). U sledećih n₁ redova se nalaze podaci o krticama iz prve grupe (u jednom redu su podaci o jednoj krtici). U svakom redu se nalaze po dva realna broja koji označavaju udaljenost krtice od ugla livade (na početku, pre nego što započne kopanje kanala) i brzinu kojom ta krtica kopa tunel. U sledećih n₂ redova se nalaze podaci o krticama iz druge grupe. Udaljenosti i brzine su između 0 i 1000000.

Izlaz:

(Izlazne podatke upisati u datoteku krtice.out) U svakom od n₁ + n₂ redova treba ispisati po jedan broj koji označava vreme koliko odgovarajuća krtica (iz ulazne datoteke) sama kopa tunel. Vremena odgovaraju krticama po redosledu kojim su navedene u ulazu, zaokruženo na dve decimale. Dozvoljena greška je 0.01.

Primer:

2 3
1 4
2 5.1
4.5 3.6
1 1
5 0.5

4.50
0.88
-1.00
1.00
-1.00

Napomena:

Nije moguće da dve krtice stignu u istom trenutku kopajući tunele.

#include <algorithm>
#include <iostream>
#include <cstdlib>

#define TOLERANCIJA 0.01f

using namespace std;

typedef struct TKrtica {
  double brzina;
  double poz;
  double vreme;
  int id;
} Krtica;

bool porediPoPoziciji(const Krtica& left, const Krtica& right) {
  return left.poz < right.poz;
}

bool porediPoId(const Krtica& left, const Krtica& right) {
  return left.id < right.id;
}

int brojKrticaH;
int brojKrticaV;
Krtica* h;
Krtica* v;

void ulaz() {
  freopen("krtice.in", "r", stdin);
  freopen("krtice.out", "w", stdout);
  scanf("%d %d", &brojKrticaV, &brojKrticaH);
  v = (Krtica*) malloc(sizeof(Krtica) * brojKrticaV);
  h = (Krtica*) malloc(sizeof(Krtica) * brojKrticaH);

  for (int i=0; i<brojKrticaV; i++) {
    scanf("%lf %lf", &v[i].poz, &v[i].brzina);
    v[i].vreme = 0.0f;
    v[i].id = i;
  }

  for (int i=0; i<brojKrticaH; i++) {
    scanf("%lf %lf", &h[i].poz, &h[i].brzina);
    h[i].vreme = 0.0f;
    h[i].id = i;
  }
}

void obrada() {
  sort(h, h+brojKrticaH, porediPoPoziciji);
  sort(v, v+brojKrticaV, porediPoPoziciji);
  int nextV = 0;
  int nextH = 0;

  while (nextV < brojKrticaV || nextH < brojKrticaH) {
    if (nextV == brojKrticaV) {
      h[nextH++].vreme = -1.0;
    } else if (nextH == brojKrticaH) {
      v[nextV++].vreme = -1.0;
    } else {
      double tV = h[nextH].poz / v[nextV].brzina;
      double tH = v[nextV].poz / h[nextH].brzina;
      if (tV > tH) {
        v[nextV++].vreme = tV;
      } else if (tV < tH) {
        h[nextH++].vreme = tH;
      } else {
        fprintf(
        stderr,
        "Nepravilan slucaj! Krtice %d i %d se susrecu u istom trenutku %lf!",
        nextV, nextH, tV);
        h[nextH].vreme = v[nextV].vreme = -1.0;
      }
    }
  }
}

void izlaz() {
  sort(h, h+brojKrticaH, porediPoId);
  sort(v, v+brojKrticaV, porediPoId);

  for (int i=0; i<brojKrticaV; i++)
    printf("%lf\n", v[i].vreme);

  for (int i=0; i<brojKrticaH; i++)
    printf("%lf\n", h[i].vreme);
}

bool jednako(double a, double b) {
  return (a + TOLERANCIJA > b) && (b + TOLERANCIJA > a);
}

void tester(const char* testovi) {
  char ulaz[512];
  char izlaz[512];

  FILE* fTestovi = fopen(testovi, "r");
  int count = 1;

  while (!feof(fTestovi)) {
    if (fscanf(fTestovi, "%s %s", ulaz, izlaz) <= 0)
      break; // kraj testova        
    printf("Testiram za: Ulaz %s Izlaz: %s Rezultat: ", ulaz, izlaz);
    try {
      // pripremi ulaz
      fclose(fopen("krtice.out", "w"));
      FILE* fUlaz = fopen(ulaz, "r");
      FILE* fKrticeIn = fopen("krtice.in", "w");

      int ch;
      while ((ch = fgetc(fUlaz)) != EOF) {
        fputc(ch, fKrticeIn);
      }

      fclose(fKrticeIn);
      fclose(fUlaz);
      // pokreni program
      system("krtice.exe");
      // otvori izlaz programa i tacan izlaz
      FILE* ispravno = fopen(izlaz, "r");
      FILE* izlazPrograma;

      try {
        izlazPrograma = fopen("krtice.out", "r");
      } catch (exception) {
        fclose(ispravno);
        throw "Greska kod otvaranja fajla";
      }
      // poredi izlaze programa
      while (true) {
        double a, b;
        int fa, fb;

        fa = fscanf(ispravno, "%lf", &a);
        fb = fscanf(izlazPrograma, "%lf", &b);

        if ( (fa <= 0 && fb > 0) || (fa > 0 && fb <= 0) ) {
          throw "Razlicit EOF";
        } else if (fa < 0 && fb < 0) {
          break;
        }

        if (!jednako(a,b)) {
          printf("\n%lf != %lf\n", a, b);
          throw "Neispravan izlaz";
        }
      }
      printf("OK %d\n", count++);
    } catch (const char* exception) {
      printf("FAILED\n");
      printf("\tZASTO: %s\n", exception);
    }
  }

  fclose(fTestovi);
}

int main(int argc, char** argv) {
  if (argc == 1) {
    ulaz();
    obrada();
    izlaz();
  } else {
    tester(argv[1]);
  }
  return 0;
}