TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

sanke.cpp    3,570 b      izvorni kod rešenja
sanke.tests.rar    71,642 b      test primeri
sanke.checker.pas    303 b      izvorni kod programa za testiranje

zadatak: Sanke

Učiteljica Danka je odlučila da svoje đake odvede na sankanje. 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žnju planinu. Kada su došli, ona je zamolila svakog đaka da joj kaže odakle će početi da se sanka, i u kom pravcu će se spuštati. Kako je Danka veoma pametna učiteljica, ona je na osnovu reljefa planine i te dve informacije zaključila i koliko brzo će ići sanke svakog učenika. 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. 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 tako da to važi.

Ulaz:

(Ulazni podaci se nalaze u datoteci sanke.in) U prvom redu datoteke se nalaze dva broja x i y (0 ≤ x, y ≤ 104) i oni predstavljaju koordinate učiteljice. U drugom redu se nalaze brojevi n ( 5 ≤ n ≤ 1000) i k (1 ≤ kn). U svakom od narednih n redova se nalaze 4 broja : prva dva broja xs[i], ys[i] ( 0 ≤ xs[i], ys[i] ≤ 104) označavaju početnu poziciju đaka, a druga dva broja xk[i], yk[i] (0 ≤ xk[i], yk[i] ≤ 104) mesto na kome će se đak naći posle 1 sekunde spuštanja.

Napomena: svi đaci se spuštaju pravolinijski, i nijedan đak neće "pregaziti" učiteljicu.

Izlaz:

(Izlazne podatke upisati u datoteku sanke.out) U izlaznu datoteku treba ispisati traženu najmanju moguću daljinu na 5 decimala.

Primer 1:

sanke.in      sanke.out
6 7
5 4
1 4 1 11
4 12 10 10
4 9 4 7
2 4 10 4
3 1 9 1
        
5.00000

Primer 2:

sanke.in      sanke.out
7 7
5 3
2 1 2 7
4 1 4 5
6 1 6 10
8 1 8 3
10 1 10 5
        
3.01591
fajl: sanke.cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

const double Pi = 3.1415926535897932384626433832795;

const long MaxN = 1001;

string fajl_in = "sanke.in";
string fajl_out = "sanke.out";


struct Event{
  double time;
  bool usao;
  
  Event(double t, bool in):time(t), usao(in){}
  
  friend bool operator<(const Event &a, const Event &b){
    if (fabs(a.time - b.time) < 1e-9) return a.usao && !b.usao;
    else return a.time < b.time;
  }
};


double cx, cy;

int n;
double mx[MaxN], my[MaxN];
double px[MaxN], py[MaxN];
double speed[MaxN];

int K;


double dist(double x1, double y1, double x2, double y2){
  return sqrt( (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

bool intersection(double px, double py, double qx, double qy, double r, double &x1, double &y1, double &x2, double &y2){
  double A = qy - py, B = px - qx, C =  px * qy - py * qx;
  double A1 = -B, B1 = A, C1 = A1 * cx + B1 * cy;
  
  double d = A * B1 - A1 * B;
  double dx = C * B1 - C1 * B;
  double dy = A * C1 - A1 * C;
  
  double xpr = dx / d, ypr = dy / d;
  
  double udaljenost = dist(xpr, ypr, cx, cy);
  if (udaljenost > r + 1e-9) return false;
  else{
    double alfa = acos(udaljenost / r);
    
    double tng = atan2(ypr - cy, xpr - cx);
    if (tng < 0) tng += 2 * Pi;
    
    double u1 = tng - alfa;
    if (u1 < 0) u1 += 2 * Pi;
    
    double u2 = tng + alfa;
    if (u2 >= 2 * Pi) u2 -= 2 * Pi;
    
    x1 = cx + r * cos(u1); y1 = cy + r * sin(u1);
    x2 = cx + r * cos(u2); y2 = cy + r * sin(u2);
      
    return true;
  }
}


bool solve(double r){
  vector<Event> dogadjaj;
  for (int i = 0; i < n; i++){
    double x1, y1, x2, y2;
    
    if (intersection(mx[i], my[i], px[i], py[i], r, x1, y1, x2, y2)){  
      if (dist(mx[i], my[i], cx, cy) < r + 1e-9){   // da li je djak vec unutra
        dogadjaj.push_back(Event(0.0, true));
        if (px[i] != mx[i]){
          if ((x1 - mx[i]) / (px[i] - mx[i]) > 0)  dogadjaj.push_back(Event(dist(x1, y1, mx[i], my[i]) / speed[i], false));
          else  dogadjaj.push_back(Event(dist(x2, y2, mx[i], my[i]) / speed[i], false));
        }
        else{
          if ((y1 - my[i]) / (py[i] - my[i]) > 0)  dogadjaj.push_back(Event(dist(x1, y1, mx[i], my[i]) / speed[i], false));
          else  dogadjaj.push_back(Event(dist(x2, y2, mx[i], my[i]) / speed[i], false));
        }
      }
      else if ((px[i] != mx[i] && (x1 - mx[i]) / (px[i] - mx[i]) > 0) || (py[i] != my[i] && (y1 - my[i]) / (py[i] - my[i]) > 0)){
        double t1 = dist(x1, y1, mx[i], my[i]) / speed[i];
        double t2 = dist(x2, y2, mx[i], my[i]) / speed[i];
        if (t1 > t2) swap(t1, t2);
        dogadjaj.push_back(Event(t1, true));
        dogadjaj.push_back(Event(t2, false));
      }
    
    }
  }
  
  sort(dogadjaj.begin(), dogadjaj.end());
  
  int unutra = 0;
  for (int i = 0; i < dogadjaj.size(); i++){
    if (dogadjaj[i].usao) unutra++;
    else unutra--;
    
    if (unutra == K) return true;
  }
  
  return false;
}


void init(){
  FILE *f;
  f = fopen(fajl_in.c_str(), "r");
  fscanf(f, "%lf %lf", &cx, &cy);
  fscanf(f, "%d %d", &n, &K);
  for (int i = 0; i < n; i++){
    fscanf(f, "%lf %lf %lf %lf", &mx[i], &my[i], &px[i], &py[i]);
    speed[i] = dist(mx[i], my[i], px[i], py[i]);
  }
  fclose(f);
}

int main(){
  init();
  
  double l = 0.00001, r = 15000.0;
  for (int korak = 0; korak < 100; korak++){
    double m = (l + r) / 2.0;
    if (solve(m)) r = m;
    else l = m;
  }
  
  FILE *f;
  f = fopen(fajl_out.c_str(), "w");
  fprintf(f, "%.5lf\n", l);
  fclose(f);
  
//  int asd; cin >> asd;
  return 0;
}