summaryrefslogtreecommitdiffstats
path: root/inf/rtk/2021-šolsko-delo/dos/3.c
diff options
context:
space:
mode:
Diffstat (limited to 'inf/rtk/2021-šolsko-delo/dos/3.c')
-rw-r--r--inf/rtk/2021-šolsko-delo/dos/3.c86
1 files changed, 86 insertions, 0 deletions
diff --git a/inf/rtk/2021-šolsko-delo/dos/3.c b/inf/rtk/2021-šolsko-delo/dos/3.c
new file mode 100644
index 0000000..9a2b186
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/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