diff options
Diffstat (limited to 'inf/rtk/2021-šolsko-delo/3.c')
| -rw-r--r-- | inf/rtk/2021-šolsko-delo/3.c | 86 |
1 files changed, 86 insertions, 0 deletions
diff --git a/inf/rtk/2021-šolsko-delo/3.c b/inf/rtk/2021-šolsko-delo/3.c new file mode 100644 index 0000000..3856d86 --- /dev/null +++ b/inf/rtk/2021-šolsko-delo/3.c @@ -0,0 +1,86 @@ +#include <stdio.h> +#include <stdlib.h> +#include <limits.h> /* ce te knjiznice ni, definiraj INT_MAX */ +#define abs(e) ((e) < (0 - (e)) ? 0 - (e) : (e)) /* da ne potrebujemo matematicne knjiznice - da rocni link matematike -lm ni potreben, definiramo absolutno vrednost stevila v preprocesorju */ +#define pot(iks,ipsilon,x,y) (abs(iks-x)+abs(ipsilon-y)) /* definiramo podano enacbo za pot, zaradi lepe berljivosti kode in zaradi hitrejsega delovanja programa kot preprocesorsko definicijo */ + +struct koord { /* definiramo strukturo para koordinat, kot je to v navodilu */ + int x; + int y; +}; + +struct koord * podprogram ( + struct koord * ss, /* seznam koordinat stalnih strank */ + size_t sss, /* stevilo stalnih strank */ + struct koord * mc, /* seznam koordinat moznih central */ + size_t mcs /* stevilo moznih central */ + ) { + int i = 0; /* indeks pri iteracijah */ + int j = 0; /* indeks pri gnezdenih iteracijah 1. globine */ + int s = 0; /* sestevek poti za trenutno pot */ + int os = INT_MAX; /* stari sestevek */ + struct koord * o; /* kazalec na trenutno najboljso centralo */ + for (i = 0; i < mcs; i++) { /* za vsako mozno centralo */ + s = 0; /* resetiramo sestevek poti */ + for (j = 0; j < sss; j++) /* za vsako stalno stranko */ + s += pot(mc[i].x, mc[i].y, ss[j].x, ss[j].y); /* povecamo sestevek poti */ + if (s < os) { /* ce smo nasli novo najboljso pot - beri: najkrajso */ + os = s; /* nastavimo staro pot na trenutno */ + o = &mc[i]; /* nastavimo kazalec na odgovor na trenutno centralo */ + } + } + return o; /* vrnemo kazalec z najbolj primerno centralo */ +} + +/* vhodni podatki v standardni vhod - na prvi vrstici so stalne stranke, na drugi pa mozne centrale. koncaj z EOF. + * 1,2 1,3 1,4 6,2 8,3 1,6 2,6 1,6 + * 6,2 7,2 5,2 6,1 + * */ +#if __INCLUDE_LEVEL__ == 0 +int main (int argc, char ** argv) { + struct koord * k = malloc(sizeof(struct koord)*1); /* inicializiramo spomin */ + char * b = malloc(sizeof(char)*1); /* za hitrost ves vhod programa najprej shranimo v delovni spomin, inicializiramo odlagalisce za to */ + size_t d = 0; /* dolzina stalnih strank */ + size_t z = 0; /* zapisanih bajtov in kasneje dolzina moznih central */ + char * p; /* kazalec za strtol */ + struct koord * o; /* odgovor podprograma */ + char c = fgetc(stdin); /* zacasni znak za branje v spomin iz standardnega vhoda */ + while (!feof(stdin)) { /* dokler jedro operacijskega sistema ne nastavi zastavice z napako, da je konec vhoda */ + b = realloc(b, sizeof(char)*(z+2)); /* povecamo spomin. POMEMBNO: tega ne delaj tako, ce gre za pomembno stvar. ce zmanjka delovnega spomina, bo b NULL in starega spomina ne bomo mogli sprostiti, torej bo spominska luknja ali se huje; segmentation violation. ceprav, ce je spomina zmanjkalo, nas bo itak prej ali slej ubil OOM morilec - uff, kaksen spis :=) */ + b[z++] = c; /* zapisemo znak */ + c = fgetc(stdin); /* dobimo nov znak, ce smo na koncu bomo potem izsli iz while() */ + } + if (b[z-1] == '\n') /* ce se vnos konca z EOL */ + z--; /* damo EOL stran */ + if (b[z-1] == '\r') /* ce je bil to inferioren operacijski sistem, bo EOL CRLF, zato pocistimo se to */ + z--; + b[z] = '\0'; /* z null-terminatorjem koncamo C-niz */ + z = 0; /* pripravimo z na ponovno uporabo */ + p = b; /* nastavimo kazalec. ce bi ga na zacetku, ne bi bilo vec okej, ker bi realloc lahko spremenil lokacijo b. s tem sem se pravzaprav relativno dolgo zafrkaval */ + do { /* delamo malo drugacen while(), tu se bo "condition" preveril na koncu */ + k = realloc(k, sizeof(struct koord)*(z+d+2)); /* povecamo velikost spomina */ + k[z+d].x = strtol(p, &p, 10); /* izluscimo naslednje celo stevilo iz niza */ + p++; /* preskocimo locilo (vejico) */ + k[z+d].y = strtol(p, &p, 10); /* izluščimo se y koordinato */ + if (z > 0) /* ce pisemo stalne stranke */ + z++; /* vecamo njihovo stevilo */ + else /* ce pa pisemo mozne centrale */ + d++; /* pa vecamo njihovo stevilo */ + if (p[0] == '\r') /* spet moramo poskrbeti, da program dela na slabsih operacijskih sistemih - beri: windows */ + p++; /* preskocimo CR */ + if (p[0] == '\n') /* ce smo na koncu prve vrstice */ + z++; /* zacnemo pisati mozne centrale */ + p++; /* gremo na naslednji znak niza. */ + } while (p[-1] != '\0'); /* dokler ne pridemo do konca niza */ + o = podprogram(k, + d, + &(k[d]), /* lahko bi bilo tudi k+d ampak meni tako izgleda bolj pregledno */ + z); + fprintf(stdout, "postavite centralo na {\"x\": %d, \"y\": %d}\n", o->x, o->y); + free(b); /* o sproscanju spomina sem ze pisal */ + b = NULL; /* in prav tako o moji praksi */ + free(k); + k = NULL; + return 0; /* predvidevamo, da bo program vedno delal (; hahaha */ +} +#endif |