#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