|
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.
|
logo by Igor Antolović
|
|
|
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 ≤ k ≤ n). 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;
}
|
|
|