|
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: Klizanje
|
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.
klizanje.in
|
|
klizanje.out
|
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.
|
|
fajl: klizanje.cpp
|
#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;
}
|
|
|