1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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
|
