Najkraca duz.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "e4d07d2c",
   "metadata": {},
   "source": [
    "### Najkraća putanja\n",
    "Nakon plotovanja tačaka kreiramo funkcije za brute force i optimizovani način za pronalaženje najkraće duži."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "aab4011a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "np.random.seed(2021)\n",
    "def generacija_tacaka(n, plotting=True):\n",
    "    '''n-broj tacaka'''\n",
    "    koordinate_x = np.random.randint(1,100,n)\n",
    "    koordinate_y = np.random.randint(1,100,n)\n",
    "    tacke = []\n",
    "    for x,y in zip(koordinate_x,koordinate_y):\n",
    "        tacke.append((x,y))\n",
    "    if plotting:\n",
    "        plt.figure(figsize=(8,8))\n",
    "        plt.scatter(koordinate_x,koordinate_y, s=5)\n",
    "        plt.title('Nasumične tačke u koordinatnom sistemu (0,100)')\n",
    "        plt.xlabel('x')\n",
    "        plt.ylabel('y');\n",
    "    return tacke"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "728142fd",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfQAAAHwCAYAAABQR52cAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAq3ElEQVR4nO3df5gkVXno8e+7rAvKoizuQhAQMIIJGI0y6qrRcMUbNSHBJ7kkGDXoRYxJjD+uXoPG+OtGJd7EaB5NrigoV3ER0ShXE5WgJFEfCLOiRkSEKAvoyg4r6LLRBZz3/lE10sxOz870dHdVnf5+nmeema7urjl1qrrervOecyoyE0mS1G2rmi6AJElaOQO6JEkFMKBLklQAA7okSQUwoEuSVAADuiRJBTCgqzUi4h8j4tSex0+KiPdExNERcVFEtOJ4rcv0pIg4IyKeVy87PiJuaqAs10fEkxv4v5f2bPszI+Iz4y5DUyLiCRFxTdPlGEREfCEiHtF0OXpFxMMi4otNl6MErThBarTqk/7NEbFvz7LnRcSlDRZrN5n5tMw8t+fxZ4FbgE8BL8zM2WH/z4jIiHjwMt/2EuAvgKnMfM+wy9Q1mXleZv7KMNbV1BeU5cjMf83Mh+zpdRHxuoj4wDjKtBQR8evAjsy8smfZSyPiexHxg4g4JyL2XuT9Z0XENRExGxHPWeD5vuuKiAMi4u8jYmdEbImI3517LjO/CtxWl08rYECfHKuBFzddiOXKzDMy80GZeUPTZZmTmbdn5qMy8781XZZRi4rniTK8AHj/3IOIeApwBnACcATwIOD1i7z/K8AfAl+a/8QS1vVO4A7gIOCZwN9FxLE9z58H/P4yt0fzZaY/hf8A11N92L4P7F8vex5wac9r3g7cCPwQ2Aw8oee5RwPT9XM3A2+tlx8P3LTA/3py/ffrgA8DHwB2AP8OHA28EthW/79f6XnvpcDzeh6fDlxdv/frwCN7/sfLga8CPwA+BOzT874TgS8DtwFfBB7Wp17+BUhgJ3A78DvAOuATwAxwa/33oT3vOQB4L/Dd+vmPLVQXwIvqMh8K7A38JXBDXX//B7h3nzK9DvhAz+Mj6jKuXmTfztX3zwHfBk7pqb/r6v1+EfCAnvc9Driirr8rgMfN2w9vBL4A/Ah4MPBfgW/Ur38H8M9z+wp4DvD5nvcnVfC4tq6jdwJRP/ezwGeB7VStL+dx9zH5fmC2/p+3A6/o2f5T6/q7BfjTnv+1N/C2en98t/577959Uq9nG7AVeDrwq8A363p51SKfm1+t9+EO4DvAy/vs6z+pn98BXEMV1J5KFcDurLflK/Vr7wecXZflO8CfA3v11OMXgL+mOna/Ve+n51B9VrYBpy7yebnHfpi3LWvqeu09lj8IvKnn8QnA95ZwPvk88Jx5y/quC9i3rouje55/P3Bmz+ND6vLt3fT5sss/fvOeHNNUJ4CX93n+CuAXqQLWB4EPR8Q+9XNvB96emfelOiFfsIz/++tUH951wJXAp6lahg4B3gC8a6E3RcTJVMHt94D7Ar9BFQTm/DbVSfNI4GFUJzMi4pHAOVTf9u9fr/+ihZoSM/OJ9Z8Pz8y1mfmhumzvBQ4HHkh1knlHz9veD9wHOBY4kOrkO7/sf1aX55cz8yaq5vmjqer3wfW2v2ah7R5Uvd2fAf44M8+PiCcBb6aqp4OBLcD59WsPAD4J/A1VHb0V+GRE3L9nlc8Gng/sRxXEPwK8GlgP/Afw+D0U6UTgUcDD6zI8Za6odbkeAPw8cBjVfiYzn00VtH+93h9v6VnfLwEPoQoUr4mIn6+X/ymwkapuH0715fPVPe/7GWAf7q7zdwPPAo4DnlCv60F9tuFs4Pczcz/goVRfRO4hIh4CvBB4VP26pwDXZ+angDcBH6q35eH1W84F7qI6Dh4B/ArVl+s5j6H6onp/qs/h+XU9Prgu9zsiYm2f8i7mKGC2Ph7nHEt11T3nK8BB846DpVpsXUcDP8nMb857/qdX6Jn5HaovP3tMZag/A/pkeQ3wxxGxYf4TmfmBzNyemXdl5l9RXfnMfbjuBB4cEeuzam6+bBn/818z89OZeRfV1foGqm/md1KdrI6IiP0XeN/zgLdk5hVZuS4zt/Q8/zeZ+d3M/D7w/6hO6FBdlb4rMy/PzJ9klZPfRXXS36O6Dj6Smf+ZmTuorlR/GSAiDgaeBrwgM2/NzDsz85973h4R8Vaqk/p/ycyZiIi6TC/NzO/X63wTcMpSyrNET6C6Aj81Mz9RL3smcE5mfikzd1G1ijw2Io4Afg24NjPfX+/vTVRX3705zPdl5lX1fnsa8PXMvLDeb28DvreHMp2ZmbdllSr5HPX+qffjxZm5KzNnqL5M/PIStvH1mfmjzPwKVTCYC5DPBN6Qmdvq9b2e6svInDuBN/Ycb+upvpzuyMyrgKuovhAu5E7gmIi4b72/d2tqBn5C9Vk5JiLulZnXZ+Z/LLSyiDiIqi5fkpk7M3Mb1RfC3mPh25n53sz8CVXL02H19u3KzM9QXekut88HwP5ULQi91lJ9WZsz9/d+A6x/sXXNf27u+fn/Z0ddTg3IgD5BMvNrVE3IZ8x/LiJeFhFX1x1abqNqGlxfP30a1bfsb0TEFRFx4jL+7c09f/8IuKU+Wc09huoDP99hVFeC/fQGlP/sWcfhwMsi4ra5n3pdD1hKYSPiPhHxrrrjzg+pmuX3j4i96vV8PzNv7fP2/amuat+cmXMnsA1UV/Sbe8rzqXr5sLwA+GJmfq5n2QOorsqBKu9P1cJxyPznalvq5+bcOG9dP32cmTnv+YUsuH8i4sCIOD8ivlPX7we4+zhb9vrYfVu2cM99vX2B423+Mdnvive3qJrdt0TEP0fEY+e/IDOvo+ok+TpgW71t/Y61w4F7AVt7joV3UbX0zJlfNjJzqeVdzK3sHkBvp2r9mjP39/zAvxSLrWv+c3PPz/8/+1GlGjQgA/rkeS3VFeNPT94R8QSqPOBvA+syc3+qb9ABkJnXZuYzqE48fwFcWPeY30kVrObWsxfDC1Q3UjXvD/K+N2bm/j0/96mvQpfiZVQtE4+pUwxzzfJRr/uAPi0KUJ00TwTeGxFzTdK3UJ2Ej+0pz/0ys99J+R51StVkvCcvAB4YEb3N/9+lCiBV4av9dX+qvO09nqs9sH5uTu9tGLdSfZmZW1f0Pl6mN9frflhdv8+iPs4W+L9LMX9bHlgvW7G6degkquP+Y/RJNWXmBzPzl+pyJNVnBHbflhupWovW9xwL983MYxnMco6Va6l2Xe+Xtqu4u6WD+u+bM3M7y7fYur4JrI6Io+Y9f9Xcg/pL0BqqPggakAF9wtRXFB+i6rQ1Zz+qvN4M1QfvNfR8o46IZ0XEhqyGjd1WL/4J1Qd1n4j4tYi4F1Xusu+wl2V6D/DyiDiu7mn94IiYH4QW8m7gBRHxmPp9+9bl69eMeDNVj9w5+1EF4NvqXPNr557IzK3APwJ/GxHrIuJeEfHE3pVl5qVUzcB/HxGPqevs3cBfR8SBABFxSN0reCFfBp4YEQ+MiPtRNZXvyQ6q/gRPjIgz62UfBJ4bEb9Y9x94E3B5Zl4P/ANwdET8bkSsjojfAY6har1ZyCeBYyPiNyNiNdWxs5QvGgvZj+qK7bY6uPzPec/P3x97sgl4dURsiIj1VGmlFQ8Vi4g1UY2vv1/dXP9DqmN+/useEtWcBHsDP6Y6duZedzNVSmkV/PT4+QzwVxFx34hYFRE/GxFLSTks5MvAb9atSg+maklbUL0N/8Q90xv/FzgtIo6JiHVUn9/39Wzb+yKi9/GaqPrVBHCviNgn7h4B0XddmbkT+Cjwhvrz+HjgJHp63FN1NPxsnR7SgAzok+kNVD1P53yaKlB9k6rJ8sfcs0n1qcBVEXE7VQe5UzLzx3Wz8h9SBd/vUF0xDGVylcz8MFX++oNUAetjVB329vS+aaoWiHdQXTFfR91hro/XAefWTaC/TZUfvjfVlfVlVM3jvZ5NlVv9BlWv45csUIaLgedSdcY7jqr14zrgsrqZ+Z/o0/mnfu+HqDpGbaZ/kJ3/vtuoeqI/LSL+V2ZeAvwZVWe2rVStHafUr91O1ZLwMqpm+FcAJ2bmLX3WfQtwMnBm/fqjqHpjD+L1wCOpWoA+SXWi7/VmqgB9W0T068DZ68+pOnx+lWoUxZfqZcPwbOD6ep+9gKo1Yb69qerlFqq0wIHAq+rnPlz/3h4Rc/n336O6Ev061fF5IVWnxUH8NVVO/Waqznbn7eH176Knf0FWHffeQtXHYUv989qe1x/GPffzZ6i+sDwOOKv++4lLXNcfUn2utlF9CfuDug/DnGdSjf7QCswNJZEkFS4iPk81EuLKPbxuDVXnw4fVV/ejLNMvAGdl5m59FLQ8BnRJkgpgk7skSQUwoEuSVAADuiRJBTCgS5JUgNVNF2Al1q9fn0cccUTTxZAkaWw2b958S2buNolXpwP6EUccwfT0dNPFkCRpbCJi/tTNgE3ukiQVwYAuSVIBDOiSJBXAgC5JUgEM6JIkFcCALklSAUYW0CPinIjYFhFf61l2QERcHBHX1r/X9Tz3yoi4LiKuWeRe0ZIkaQGjvEJ/H9V9tHudAVySmUcBl9SPiYhjqO7VfGz9nr+NiL1GWDZJkooysoCemf8CfH/e4pOAc+u/zwWe3rP8/MzclZnfBq4DHj2qskmSVJpx59APysytAPXvA+vlhwA39rzupnrZbiLi+RExHRHTMzMzIy2sJEld0ZZOcbHAslzohZl5VmZOZebUhg27TWUrSdJEGndAvzkiDgaof2+rl98EHNbzukOB7465bJIkdda4A/pFwKn136cCH+9ZfkpE7B0RRwJHAf825rJJktRZI7vbWkRsAo4H1kfETcBrgTOBCyLiNOAG4GSAzLwqIi4Avg7cBfxRZv5kVGWTJKk0IwvomfmMPk+d0Of1bwTeOKrySJJUsrZ0ipMkSStgQFdnzc4mMzt2kbnggAhJmigja3KXRml2NnnGuy9j85ZbOe7wdWw6fSOrVi00+lGSJoNX6Oqk7TvvYPOWW7lrNtm85Va277yj6SJJUqMM6Oqk9WvXcNzh61i9Kjju8HWsX7um6SJJUqNsclcnRQSbTt/I9p13sH7tGiJsbp9Us7PpcSBhQFeHrVoVbNhv76aLoQbZl0K6m03ukjrLvhTS3QzokjrLvhTS3Wxyl9RZ9qWQ7mZAl9Rp9qWQKja5S5JUAAO6JEkFMKBLklQAA7okSQUwoEuSVAADuiRJBTCgS1ILzc4mMzt2kZlNF0Ud4Th0SWoZ56jXILxCl6SWcY56DcKALkkt4xz1GoRN7pLUMs5Rv2ezs2n9zGNAl6QWco76/uxjsDCb3CVJnWIfg4UZ0CVJnWIfg4XZ5C5J6hT7GCzMK3QNhZNgSOpnFOeHuT4GBvO7eYWuFbODiqR+PD+Mj1foWjE7qEjqx/PD+BjQtWJ2UJHUj+eH8Yku5zynpqZyenq66WIIJ3mQ1J/nh+GKiM2ZOTV/uTl0DYWTYEjqx/PDeNjkLklSAQzokiQVwIAuLdOkjrlfynZPat1otDyulsYcurQMkzqmdinbPal1o9HyuFo6r9ClZZjUMbVL2e5JrRuNlsfV0hnQpWWY1DG1S9nuSa0bjZbH1dI5Dl1apkkdU3vXXbNcN3M7Rx+0llWrFr4WmNS60Wh5XN2T49ClIZnEMbWzs8kzz758j3nMSawbjZ7H1dLY5C5pj8xjSu1nQJe0R+YxpfazyV3SHkUEm07fOPQ8prlRaXgM6JKWZNh5TMcXS8Nlk7ukRpiXl4bLgC6pEeblpeGyyb1hXc0hdrXcao9R5eWlSWVAb1BXc4hdLbfax/HF0vDY5N6gruYQu1puSSqZAb1BXc0hdrXcklQy53JvWFdz0V0ttyR1nXO5t1RXc4hdLbcklcomd0mSCmBAlySpAAZ0SZIKYECXJKkABnRJkgpgQJckqQAGdEmSCmBAl6QWmp1NZnbsosuTf2m8nFhGklrGGyBpEF6hS1LLeAMkDcKALkkt4w2QNAib3CWpZSKCTadv9AZIWhYDuiS1kDdA0nLZ5C5JUgEM6JIkFcCALmlsHFstjY45dElj4dhqabS8Qpc0Fo6tlkbLgC5pLBxbLY2WTe6SxsKx1dJoGdAljY1jq6XRscldkqQCNBLQI+KlEXFVRHwtIjZFxD4RcUBEXBwR19a/1zVRNkmSumjsAT0iDgFeBExl5kOBvYBTgDOASzLzKOCS+rEkSVqCpprcVwP3jojVwH2A7wInAefWz58LPL2ZoklS85yER8s19oCemd8B/hK4AdgK/CAzPwMclJlb69dsBQ4cd9kkqQ3mJuF57Jsv4ZSzLmN21qCuPWuiyX0d1dX4kcADgH0j4lnLeP/zI2I6IqZnZmZGVUxJaoyT8GgQTTS5Pxn4dmbOZOadwEeBxwE3R8TBAPXvbQu9OTPPysypzJzasGHD2AotSePiJDwaRBPj0G8ANkbEfYAfAScA08BO4FTgzPr3xxsomyQ1zkl4NIixB/TMvDwiLgS+BNwFXAmcBawFLoiI06iC/snjLpsktYWT8Gi5GpkpLjNfC7x23uJdVFfrkiRpmZwpTpKkAhjQJUkqgAFdkqQCGNAlSSqAAV2SpAIY0CVJKoABXZKkAhjQJUkqgAFdkqQCGNClFvDe15JWqpGpXyXdbe7e15u33Mpxh69j0+kbWbXKm3FIWh6v0KWGee9rScNgQJca5r2vJQ2DTe4aitnZ9N7NA2rrva/dp1K3GNC1YuaAV65t9752n0rdY5O7VswccHncp1L3GNC1YuaAy+M+lbonujzudWpqKqenp5suhjDfWiL3qdROEbE5M6fmL/cKXUMxlwP2xD8e45iIxn0qdYud4qSOscOapIV4hS51jB3WJC3EgC51jB3WJC3EJnepY9o6EY2kZhnQpQ5q20Q0kppnk7skSQUwoEuSVAAD+gQaxxjmrrJuJHWVOfQJ4xjm/qwbSV3mFfqEcQxzf9aNpC4zoE8YxzD3Z91I6jJvzjKBvOlGf9aNpDltPR/0uzmLOfQJ5Bjm/qwbSdDNPjU2uUuSNE8X+9QY0CVJmqeLfWpscpc0NG3NOaoyyftnudvexXsmGNAlDUUXc46TZJL3z6Db3rU+NTa5SxqKLuYcJ8kk759J2XYDuqSh6GLOcZJM8v6ZlG13HLo0ZiXnMZvYtpLrc76Vbusk1dV8JW2749ClFig9jznunGPp9dlrGNvatZzwME3CttvkLo3RpOTyxmWS6nOStlWDMaBLYzQpubxxmaT6nKRt1WDMoUtjVlIurw0mqT4naVvVX78culfoLTc7m8zs2EWXv3jpnuZyeZ6Qh2MU9dnWz53Hzni19Tjox05xLTZJHX6ktvBzJ+jmceAVeovZCUYaPz93gm4eBwb0FrMTjDR+fu4E3TwO7BTXcnaCEXgcjJv1LWjvceDEMh01CZMhaHFdzOV1nZ87QfeOA5vcpZbrYi5P0vgZ0KWW62IuT9L42eQutVxEsOn0ja3M5Umj0NbcddsZ0KUO6FouTxqUfUYGZ5O7JKk17DMyOAO6JKk17DMyOJvcJUmtYZ+RwRnQJUmtYp+RwdjkLklSAQzokiQVwICu1uravYglqUnm0NVKjkWVpOXxCl2t5FhUSVoeA7paybGokrQ8NrmrlRyLKk0u53IfjAFdreVYVGny2H9mcDa5S5Jaw/4zgzOgS5Jaw/4zg7PJXZLUGvafGZwBXZLUKvafGYxN7pIkFcCALklSAQzokiQVwIAuSVIBDOiSJBWgkYAeEftHxIUR8Y2IuDoiHhsRB0TExRFxbf17XRNlkySpi5q6Qn878KnM/Dng4cDVwBnAJZl5FHBJ/ViSJC3B2AN6RNwXeCJwNkBm3pGZtwEnAefWLzsXePq4yyZJUlc1cYX+IGAGeG9EXBkR74mIfYGDMnMrQP37wAbKJklSJzUR0FcDjwT+LjMfAexkGc3rEfH8iJiOiOmZmZlRlVGSpE5pIqDfBNyUmZfXjy+kCvA3R8TBAPXvbQu9OTPPysypzJzasGHDWAosSVLbjT2gZ+b3gBsj4iH1ohOArwMXAafWy04FPj7usqn7ZmeTmR27yMymi6IW8zhRiZq6OcsfA+dFxBrgW8Bzqb5cXBARpwE3ACc3VDZ11Oxs8ox3X8bmLbdy3OHr2HT6Rlat8k5NuiePE5WqkYCemV8GphZ46oQxF0UF2b7zDjZvuZW7ZpPNW25l+847vGOTduNxolI5U5yKsX7tGo47fB2rVwXHHb6O9WvXNF0ktZDHiUoVXc4hTU1N5fT0dNPF0BLMzibbd97B+rVriBhd8+a4/s+wdbXcXWV9q8siYnNm7tbK3VQOXRNknDnLVauic82n5nTHr4vHibQnNrlr5BbKWepu1o+kYTCga+TMWS7O+pE0DObQNRbmLBdn/UhaKnPoapQ5y8VZP5JWyiZ3SZIKYECXJKkABnR1hvNvt5/7SGqOOXR1gmO12899JDXLK3R1gmO12899JDXLgK5OcKx2+7mPpGY5Dl2d4Vjt9nMfSaPXbxy6V+jqjLmx2k0HCjt+9bfcfWRdSsNjpzhpGez4NTzWpTRcXqFLy2DHr+GxLqXhMqBLy2DHr+GxLqXhslOctEx2/Boe61KjMv/YKulY8+Ys0pB4I5XhsS41CvP7Z5x32mN45tmXF99fwyZ3SVJR5vfPuG7m9onor2FAlyQVZX7/jKMPWjsR/TXMoUuSinPXXbNcN3M7Rx+0llWrVo0kh95UXt4cuiRpIszO5oI582H212jjPAo2uUuSijKOOQ7aOI+CAV2SVJRxzHHQxnkUzKFLy1TSeFapVOP4nJpDlzqsjXkzSbsbxxwHbZtHwSZ3aRnamDeTJDCgS8vSxryZJIFN7irMqHNaEcGm0zeaQ5fUOgZ0FWNc+e225c0kCWxyV0HMb0uaZHsM6BHxwohYN47CSCthflvSJFtKk/vPAFdExJeAc4BPZ5cHr6tY5rel4XPehe7Y4xV6Zr4aOAo4G3gOcG1EvCkifnbEZZOWbS6/7YlHWrm5fimPffMlnHLWZczOei3XZkvKoddX5N+rf+4C1gEXRsRbRlg2SVKD7JfSLUvJob8oIjYDbwG+APxCZv4BcBzwWyMunySpIfZL6Zal5NDXA7+ZmVt6F2bmbEScOJpiSZKaZr+UbtljQM/M1yzy3NXDLY4kqU2cd6E7HIcuSVIBDOiSJBXAgC5JUgEM6D1mZ5OZHbtw3hxJUtd4c5bauG7sIUnSKHiFXnMCBUlSlxnQa06gIEnqMpvca06gsDhv0CBp0nTtvGdA7+EECguzf4GkSdPF855N7toj+xdImjRdPO8Z0LVH9i+QNGm6eN6LLo+5npqayunp6aaLMRH2lEvqWq5pnKwbqX2W8rls63kvIjZn5tT85ebQtSSL9S/oYq5pXKwbqX2W+rns2nnPJnetWBdzTeNi3UjtM4zPZRs/2wZ0rVgXc03jYt1I7TOMz2UbP9vm0DWQ+bkj88T9WTdS+wzjc2kOXZ3XL3fkGP6FWTdS+wzjc9m2z7ZN7lq2NuaOJGnSGdC1bG3MHUnSpLPJXcvmvPeS1D4GdA2kbbkjSZp0NrlLklQAA7okSQUwoEuSVAADuiRJBTCgS5JUAAO6JEkFMKBLklQAA7oktdDsbDKzYxddvoGWxsuJZSSpZfrdAElajFfoktQy3gBJgzCgS1LLeAMkDcImd0lqGW+A1A6zs7mifbDS9y+XAV2SWsgbIDVrpf0YmugH0ViTe0TsFRFXRsQn6scHRMTFEXFt/XtdU2WTJE22lfZjaKIfRJM59BcDV/c8PgO4JDOPAi6pH0uSNHYr7cfQRD+IaGKMY0QcCpwLvBH4H5l5YkRcAxyfmVsj4mDg0sx8yGLrmZqayunp6TGUWOq+cefzpK5raw49IjZn5tT85U3l0N8GvALYr2fZQZm5FaAO6gc2UTCpRI5rlpZvpf0Yxt0PYuxN7hFxIrAtMzcP+P7nR8R0REzPzMwMuXRSmRzXLJWviRz644HfiIjrgfOBJ0XEB4Cb66Z26t/bFnpzZp6VmVOZObVhw4ZxlVnqNMc1S+VrJIf+038ecTzw8jqH/r+B7Zl5ZkScARyQma9Y7P1dyKGbtxwe63JlrD+pDG3LoS/kTOCCiDgNuAE4ueHyrJh5y+GxLlfOcc1S2RoN6Jl5KXBp/fd24IQmyzNsC+UtPaEOxrqUpMU5l/sImbccHutSkhbXaA59pcyhTxbrUpK6kUMvknnL4bEuJak/m9wlSSqAAV2SpAIY0CVJKoABXdLIzM4mMzt20eXOt1JX2ClO0kg4GZA0Xl6hSxoJbwgjjZcBXdJIOBmQNF42uUsaiYhg0+kbnQxIGhMDuqSRcTIgaXxscpckqQAGdEmSCmBAX4FSxtiWsh2SNMnMoQ+olDG2pWyHJE06r9AHVMoY21K2Q5ImnQF9QKWMsS1lOyRp0kWX86ZTU1M5PT3d2P+fnc0Vj7EdxjpWqg1lkCQtTURszsyp+cvNoa/ASsfYtiV/7VhhSeo+m9wbZP5akjQsBvQGmb+WJA2LTe4NavNc1+bV1RSPvfGyvsthQG9YG/PXbcnta/J47I2X9V0Wm9y1G3P7aorH3nhZ32UxoGs35vbVFI+98bK+y+I4dC3IvJqa4rE3XqXWd6nbBY5D1zK1MbevyeCxN14l1vek9g2wyV2SVJRJ7RtgQJckFWVS+wbY5C5JKkqb5/gYJa/QNRazs8nMjl10uROmpO6Y6xswKcEcvELXGExqBxVJGiev0DVyk9pBRZLGyYCukZvUDiqSNE42uWvkJrWDiqSytH2yGgO6xqLEySskTY4u9AWyyV2SpD3oQl8gA7okSXvQhb5ANrlLkrQHXegLZECXJGkJ2t4XyCZ3SZIKYECXJKkABnRJmsd7D6iLzKFLUo8ujDeWFuIVuiT16MJ4Y2khBnRJ6tGF8cbSQmxylzSwts9tPYgujDeWFmJAlzSQknPNbR9vLC3EJndJAzHXLLWLAV3SQMw1S+1ik7ukgQwj19yVHPwg5ezKtqkcBnRJA1tJrrkrOfhBytmVbVNZbHKX1Iiu5OAHKWdXtk1lMaBLakRXcvCDlLMr26ayRJfnKp6amsrp6emmiyFpQF3JM5tDV5tExObMnJq/3By6pMZ0Zbz3IOXsyrapHDa5S5JUAAO6JEkFMKBLklQAA7okSQUwoEuSVAADuiRJBTCgS5JUAAO6JEkFMKBLklQAA7okSQUwoEuSVAADuiRJBTCgS5JUAAO6JEkFMKBLklQAA3rDZmeTmR27yMxG11EK60LSpFrddAEm2exs8ox3X8bmLbdy3OHr2HT6RlatirGvoxTWhaRJ5hV6g7bvvIPNW27lrtlk85Zb2b7zjkbWUQrrQtIkG3tAj4jDIuJzEXF1RFwVES+ulx8QERdHxLX173XjLtu4rV+7huMOX8fqVcFxh69j/do1jayjFNaFpEkW4841RsTBwMGZ+aWI2A/YDDwdeA7w/cw8MyLOANZl5p8stq6pqamcnp4eWVlnZ5PtO+9g/do1RIym6XYY/2Mc5ewK60KD8LhRl0TE5sycmr987Dn0zNwKbK3/3hERVwOHACcBx9cvOxe4FFg0oI/SuPKxq1YFG/bbu/F1lMK60HLZ90KlaDSHHhFHAI8ALgcOqoP9XNA/sM97nh8R0xExPTMzM7KymY+VJoOfdZWisYAeEWuBjwAvycwfLvV9mXlWZk5l5tSGDRtGVj7zsdJk8LOuUjQybC0i7kUVzM/LzI/Wi2+OiIMzc2udZ9/WRNnmRASbTt9oXk0qnJ91laKJXu4BnA1cnZlv7XnqIuDU+u9TgY+Pu2zzzeVj/YBLZfOzrhI0cYX+eODZwL9HxJfrZa8CzgQuiIjTgBuAkxsomyRJndREL/fPA/2+Bp8wzrJIklQKZ4qTJKkABnRJkgpgQJckqQAGdEmSCmBAlySpAAZ0jcTsbDKzYxfjvvmPJC1FieeoRmaKU9m82YWkNiv1HOUVuobOm11IarNSz1EGdA2dN7uQ1GalnqOiy/mDqampnJ6ebroYWsDsbHqzC0mtNY5z1Kj+R0Rszsyp+cvNoWsk5m52IUltNOpzVBN5epvcJUkasiby9AZ0SZKGrIk8vU3ukqRGldjnJiLYdPrGsW6XAV2S1JhSx4TD+PsS2eQuSWpMqWPCm2BAlyQ1ptQx4U2wyV2S1Jgmcs2lMqBLkhrlvBXDYZO7JEkFMKBLklQAA7qkgZV4T+k2s761GHPokgZS8vjhNrK+tSdeoUsaiOOHx8v61p4Y0CUNxPHD42V9a0+8H7qkgZU4B3ebWd+C/vdD9wq9QJPScWZStrPN5sYPG1zGw/rWYuwUV5hJ6TgzKdspSUvlFXphJqXjzKRspyQtlQG9MJPScWZStlOSlspOcQWalI4zk7KdktSrX6c4c+gFmpQbHUzKdkrSUtjkLklSAQzokiQVwIAuSVIBDOiSJBXAgC5JUgEM6JIkFcCALklSAQzokiQVwIAuSVIBDOiSJBXAgC4twnuuCzwO1A3O5S714T3XBR4H6g6v0KU+vOe6wONA3WFAl/rwnusCjwN1h/dD7xjvAT5e1rfA40Dt4v3QC2Aub/y857rA40DdYJN7h5jLkyT1Y0DvEHN5kqR+bHLvkIhg0+kbzeVJknZjQO8Yc3mSpIXY5C5JUgEM6JIkFcCALklSAQzoGglvZiFJ42WnOA2dE+BI0vh5ha6hcwIcSRo/A7qGzglwJGn8bHLX0LV5AhxvsiGpVAZ0jUQbJ8Axty+pZDa5a2KY25dUMgO6Joa5fUkls8ldRVksR97m3L4krZQBXcVYSo68jbl9SRoGm9xVDHPkkiaZAV3FMEcuaZLZ5K5imCOXNMkM6CqKOXJJk8omd0mSCmBAlySpAAZ0SZIKYECXJKkABnRJkgrQuoAeEU+NiGsi4rqIOKPp8kiS1AWtCugRsRfwTuBpwDHAMyLimGZLJUlS+7UqoAOPBq7LzG9l5h3A+cBJDZdJkqTWa1tAPwS4sefxTfUySZK0iLYF9IXm6sx7vCDi+RExHRHTMzMzYyqWJEnt1raAfhNwWM/jQ4Hv9r4gM8/KzKnMnNqwYcNYCydJUlu1LaBfARwVEUdGxBrgFOCihsskSVLrtermLJl5V0S8EPg0sBdwTmZe1XCxJElqvVYFdIDM/AfgH5ouhyRJXdK2JndJkjQAA7okSQWIzNzzq1oqImaALStYxXrgliEVR9bnsFmfw2NdDpf1OVzLrc/DM3O3YV6dDugrFRHTmTnVdDlKYX0Ol/U5PNblcFmfwzWs+rTJXZKkAhjQJUkqwKQH9LOaLkBhrM/hsj6Hx7ocLutzuIZSnxOdQ5ckqRSTfoUuSVIRJjagR8RTI+KaiLguIs5oujxdEhGHRcTnIuLqiLgqIl5cLz8gIi6OiGvr3+uaLmuXRMReEXFlRHyifmx9Digi9o+ICyPiG/Vx+ljrczAR8dL6c/61iNgUEftYl0sXEedExLaI+FrPsr71FxGvrOPSNRHxlOX8r4kM6BGxF/BO4GnAMcAzIuKYZkvVKXcBL8vMnwc2An9U198ZwCWZeRRwSf1YS/di4Oqex9bn4N4OfCozfw54OFW9Wp/LFBGHAC8CpjLzoVT32DgF63I53gc8dd6yBeuvPo+eAhxbv+dv63i1JBMZ0IFHA9dl5rcy8w7gfOCkhsvUGZm5NTO/VP+9g+pkeQhVHZ5bv+xc4OmNFLCDIuJQ4NeA9/Qstj4HEBH3BZ4InA2QmXdk5m1Yn4NaDdw7IlYD96G6pbV1uUSZ+S/A9+ct7ld/JwHnZ+auzPw2cB1VvFqSSQ3ohwA39jy+qV6mZYqII4BHAJcDB2XmVqiCPnBgg0XrmrcBrwBme5ZZn4N5EDADvLdOYbwnIvbF+ly2zPwO8JfADcBW4AeZ+Rmsy5XqV38rik2TGtBjgWV291+miFgLfAR4SWb+sOnydFVEnAhsy8zNTZelEKuBRwJ/l5mPAHZik/BA6tzuScCRwAOAfSPiWc2Wqmgrik2TGtBvAg7reXwoVTOSligi7kUVzM/LzI/Wi2+OiIPr5w8GtjVVvo55PPAbEXE9VfrnSRHxAazPQd0E3JSZl9ePL6QK8Nbn8j0Z+HZmzmTmncBHgcdhXa5Uv/pbUWya1IB+BXBURBwZEWuoOiFc1HCZOiMigio/eXVmvrXnqYuAU+u/TwU+Pu6ydVFmvjIzD83MI6iOxc9m5rOwPgeSmd8DboyIh9SLTgC+jvU5iBuAjRFxn/pzfwJVnxnrcmX61d9FwCkRsXdEHAkcBfzbUlc6sRPLRMSvUuUt9wLOycw3Nlui7oiIXwL+Ffh37s75vooqj34B8ECqE8HJmTm/M4gWERHHAy/PzBMj4v5YnwOJiF+k6mC4BvgW8FyqCxjrc5ki4vXA71CNbrkSeB6wFutySSJiE3A81R3VbgZeC3yMPvUXEX8K/Heq+n5JZv7jkv/XpAZ0SZJKMqlN7pIkFcWALklSAQzokiQVwIAuSVIBDOiSJBXAgC5JUgEM6JIkFcCALmnJIuJREfHV+p7Y+9b3yX5o0+WS5MQykpYpIv4c2Ae4N9Wc6W9uuEiSMKBLWqb6/gdXAD8GHpeZP2m4SJKwyV3S8h1ANZf3flRX6pJawCt0ScsSERdR3eb1SODgzHxhw0WSBKxuugCSuiMifg+4KzM/GBF7AV+MiCdl5mebLps06bxClySpAObQJUkqgAFdkqQCGNAlSSqAAV2SpAIY0CVJKoABXZKkAhjQJUkqgAFdkqQC/H+fbS8XYIOaggAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tacke = generacija_tacaka(100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a3c1835d",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "\n",
    "def povuci_sve_duzi(tacke):\n",
    "    sve_duzi = []\n",
    "    for duz in combinations(tacke,2):\n",
    "        sve_duzi.append(duz)\n",
    "#     print(f'povučeno duži: {len(sve_duzi)}')\n",
    "    return sve_duzi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "fb30cb88",
   "metadata": {},
   "outputs": [],
   "source": [
    "def izracunaj_najkracu_duz(sve_duzi):\n",
    "    \n",
    "    izracunate_duzi = dict()\n",
    "    for index in range(len(sve_duzi)):\n",
    "        x,y = sve_duzi[index]\n",
    "        izracunate_duzi[index] = []\n",
    "        x_diff = x[0]-x[1]\n",
    "        y_diff = y[0]-y[1]\n",
    "        izracunate_duzi[index].append((x_diff**2+y_diff**2)**0.5)\n",
    "    \n",
    "    minimum = min(izracunate_duzi.values())\n",
    "    \n",
    "    for key, value in izracunate_duzi.items():\n",
    "        if value==minimum:\n",
    "            return sve_duzi[key], value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "f7e454cf",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tacke najkrace duzi: ((13, 12), (54, 55))\n",
      "Duzina najkrace duzi 1.4142135623730951\n"
     ]
    }
   ],
   "source": [
    "sve_duzi = povuci_sve_duzi(tacke)\n",
    "tacke_najkrace_duzi, duz =izracunaj_najkracu_duz(sve_duzi)\n",
    "print('Tacke najkrace duzi:', tacke_najkrace_duzi)\n",
    "print('Duzina najkrace duzi', duz[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "30f27034",
   "metadata": {},
   "outputs": [],
   "source": [
    "np.random.seed(2021)\n",
    "tacke_najkrace_duzi=tacke_najkrace_duzi\n",
    "def plotovanje_tacaka_najkrace_duzi(n, tacke_najkrace_duzi=tacke_najkrace_duzi, plotting=True):\n",
    "    '''n-broj tacaka'''\n",
    "    koordinate_x = np.random.randint(1,100,n)\n",
    "    koordinate_y = np.random.randint(1,100,n)\n",
    "    tacke = []\n",
    "    for x,y in zip(koordinate_x,koordinate_y):\n",
    "        tacke.append((x,y))\n",
    "    if plotting:\n",
    "        plt.figure(figsize=(8,8))\n",
    "        plt.scatter(koordinate_x,koordinate_y, s=5)\n",
    "        plt.scatter(tacke_najkrace_duzi[0], tacke_najkrace_duzi[1], c='red', label='najbliže tačke', s=10)\n",
    "        plt.title('Nasumične tačke u koordinatnom sistemu (0,100)')\n",
    "        plt.xlabel('x')\n",
    "        plt.ylabel('y')\n",
    "        plt.legend();\n",
    "    return tacke"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "a22f7d0b",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAfQAAAHwCAYAAABQR52cAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuNCwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8QVMy6AAAACXBIWXMAAAsTAAALEwEAmpwYAAAxbklEQVR4nO3deZgkVZno/+/bQIPYLTR0w2WRxWGRRRYpRoSRQZnBZRB85KeC6KBCe7mCo14dLjDigqOiP6/jNg6CCIxAiyMufWdcUJRRYICultZhkYGrNLS0UDRb07I01Hv/iChIqqu6q7KyMjIiv5/nqScrIzMiT5yIjDfjvOdERGYiSZLqbUbVBZAkSVNnQJckqQEM6JIkNYABXZKkBjCgS5LUAAZ0SZIawICunhERP4iI41qevyIivhoRu0TEwojoif21LNMrIuLUiDihnHZIRCyroCx3RMRfVPC5V7as+7ERcXm3y1CViHhZRNxadTnaERFXR8S+VZejVUTsFRHXVF2OJuiJA6SmV3nQvycintsy7YSIuLLCYq0hM1+dmRe2PP8pcB/wQ+DkzBzu9GdGREbETpOc7b3Ap4CBzPxqp8tUN5l5cWYe1ollVfUDZTIy8xeZueu63hcRH4mIi7pRpomIiNcCKzPzhpZp74uIP0TEQxHxtYjYcC3znxMRt0bEcES8bYzXx11WRGwWEd+JiFURsTQi3jzyWmb+GniwLJ+mwIDeP9YH3lN1ISYrM0/NzBdk5p1Vl2VEZj6Smftn5v9XdVmmWxQ8TjTDicDXR55ExCuBU4FDgR2AFwAfXcv8vwLeBfxy9AsTWNY/Ak8AWwLHAv8UEXu0vH4x8N8nuT4aLTP9a/gfcAfFl+1+YNNy2gnAlS3v+TxwF/AwsBh4WctrfwoMlq/dA3y2nH4IsGyMz/qL8v+PAP8CXASsBP4T2AU4Dbi3/LzDWua9Ejih5fl84JZy3puBF7d8xgeAXwMPAZcCG7XMdziwBHgQuAbYa5x6+TmQwCrgEeBNwBzgX4Eh4IHy/21b5tkMOB+4u3z9u2PVBfA3ZZm3BTYEPgPcWdbf2cBzxinTR4CLWp7vUJZx/bVs25H6fiHwO+Dolvq7vdzuC4GtW+Y7EFhU1t8i4MBR2+HjwNXAo8BOwF8Cvynf/yXg30e2FfA24KqW+ZMieNxW1tE/AlG+9ifAT4EVFK0vF/PMPvl1YLj8zEeAU1rW/7iy/u4D/q7lszYEPlduj7vL/zds3Sblcu4FlgOvA14D/FdZL6ev5XvzmnIbrgR+D3xgnG39v8rXVwK3UgS1V1EEsNXluvyqfO8mwHllWX4P/D2wXks9Xg38A8W++9tyO72N4rtyL3DcWr4vz9oOo9ZlZlmvrfvyJcAnWp4fCvxhAseTq4C3jZo27rKA55Z1sUvL618Hzmp5vk1Zvg2rPl7W+c9f3v1jkOIA8IFxXl8E7EMRsC4B/iUiNipf+zzw+cx8HsUB+ZuT+NzXUnx55wA3AD+iaBnaBjgT+MpYM0XEGyiC218DzwOOoAgCI95IcdDcEdiL4mBGRLwY+BrFr/3Ny+UvHKspMTMPLv/dOzNnZealZdnOB7YHtqM4yHypZbavAxsDewBbUBx8R5f9jLI8f56Zyyia53ehqN+dynX/0Fjr3a5yvS8H3p2Z34iIVwCfpKinrYClwDfK924G/BvwBYo6+izwbxGxecsi3wq8E5hNEcQvAz4IzAX+L3DQOop0OLA/sHdZhleOFLUs19bAbsDzKbYzmflWiqD92nJ7fLpleX8G7EoRKD4UEbuV0/8OOICibvem+PH5wZb5/huwEc/U+bnAW4D9gJeVy3rBOOtwHvDfM3M2sCfFD5FniYhdgZOB/cv3vRK4IzN/CHwCuLRcl73LWS4EnqTYD/YFDqP4cT3iJRQ/VDen+B5+o6zHncpyfykiZo1T3rXZGRgu98cRe1CcdY/4FbDlqP1gota2rF2ApzLzv0a9/vQZemb+nuLHzzpTGRqfAb2/fAh4d0TMG/1CZl6UmSsy88nM/N8UZz4jX67VwE4RMTeL5uZrJ/GZv8jMH2XmkxRn6/MofpmvpjhY7RARm44x3wnApzNzURZuz8ylLa9/ITPvzsz7gf9DcUCH4qz0K5l5XWY+lUVO/nGKg/46lXVwWWb+MTNXUpyp/jlARGwFvBo4MTMfyMzVmfnvLbNHRHyW4qD+8swciogoy/S+zLy/XOYngKMnUp4JehnFGfhxmfmv5bRjga9l5i8z83GKVpGXRsQOwF8Bt2Xm18vtvYDi7Ls1h3lBZt5UbrdXAzdn5rfK7fY54A/rKNNZmflgFqmSn1Fun3I7/jgzH8/MIYofE38+gXX8aGY+mpm/oggGIwHyWODMzLy3XN5HKX6MjFgNfLxlf5tL8eN0ZWbeBNxE8YNwLKuB3SPieeX2XqOpGXiK4ruye0RskJl3ZOb/HWthEbElRV2+NzNXZea9FD8IW/eF32Xm+Zn5FEXL0/PL9Xs8My+nONOdbJ8PgE0pWhBazaL4sTZi5P/ZbSx/bcsa/drI66M/Z2VZTrXJgN5HMvNGiibkU0e/FhHvj4hbyg4tD1I0Dc4tXz6e4lf2byJiUUQcPomPvafl/0eB+8qD1chzKL7woz2f4kxwPK0B5Y8ty9geeH9EPDjyVy5r64kUNiI2joivlB13HqZolt80ItYrl3N/Zj4wzuybUpzVfjIzRw5g8yjO6Be3lOeH5fROORG4JjN/1jJta4qzcqDI+1O0cGwz+rXS0vK1EXeNWtbTzzMzR70+ljG3T0RsERHfiIjfl/V7Ec/sZ5NeHmuuy1Keva1XjLG/jd4nxzvjPYqi2X1pRPx7RLx09Bsy83aKTpIfAe4t1228fW17YANgecu+8BWKlp4Ro8tGZk60vGvzAGsG0EcoWr9GjPw/OvBPxNqWNfq1kddHf85silSD2mRA7z8fpjhjfPrgHREvo8gDvhGYk5mbUvyCDoDMvC0zj6E48HwK+FbZY34VRbAaWc56dC5Q3UXRvN/OfB/PzE1b/jYuz0In4v0ULRMvKVMMI83yUS57s3FaFKA4aB4OnB8RI03S91EchPdoKc8mmTneQflZdUrRZLwuJwLbRURr8//dFAGkKHyxvTanyNs+67XSduVrI1pvw7ic4sfMyLKi9fkkfbJc9l5l/b6Fcj8b43MnYvS6bFdOm7KydehIiv3+u4yTasrMSzLzz8pyJMV3BNZcl7soWovmtuwLz8vMPWjPZPaV2yg2XeuPtpt4pqWD8v97MnMFk7e2Zf0XsH5E7Dzq9ZtGnpQ/gmZS9EFQmwzofaY8o7iUotPWiNkUeb0hii/eh2j5RR0Rb4mIeVkMG3uwnPwUxRd1o4j4q4jYgCJ3Oe6wl0n6KvCBiNiv7Gm9U0SMDkJjORc4MSJeUs733LJ84zUj3kPRI3fEbIoA/GCZa/7wyAuZuRz4AfDliJgTERtExMGtC8vMKymagb8TES8p6+xc4B8iYguAiNim7BU8liXAwRGxXURsQtFUvi4rKfoTHBwRZ5XTLgHeHhH7lP0HPgFcl5l3AN8HdomIN0fE+hHxJmB3itabsfwbsEdEvD4i1qfYdybyQ2MssynO2B4sg8vfjnp99PZYlwXAByNiXkTMpUgrTXmoWETMjGJ8/SZlc/3DFPv86PftGsU1CTYEHqPYd0bedw9FSmkGPL3/XA7874h4XkTMiIg/iYiJpBzGsgR4fdmqtBNFS9qYynX4Cc9Ob/wzcHxE7B4Rcyi+vxe0rNsFEdH6fGYU/WoC2CAiNopnRkCMu6zMXAV8Gziz/D4eBBxJS497io6GPy3TQ2qTAb0/nUnR83TEjygC1X9RNFk+xrObVF8F3BQRj1B0kDs6Mx8rm5XfRRF8f09xxtCRi6tk5r9Q5K8voQhY36XosLeu+QYpWiC+RHHGfDtlh7lxfAS4sGwCfSNFfvg5FGfW11I0j7d6K0Vu9TcUvY7fO0YZfgy8naIz3n4UrR+3A9eWzcw/YZzOP+W8l1J0jFrM+EF29HwPUvREf3VEfCwzrwDOoOjMtpyitePo8r0rKFoS3k/RDH8KcHhm3jfOsu8D3gCcVb5/Z4re2O34KPBiihagf6M40Lf6JEWAfjAixuvA2ervKTp8/ppiFMUvy2md8FbgjnKbnUjRmjDahhT1ch9FWmAL4PTytX8pH1dExEj+/a8pzkRvptg/v0XRabEd/0CRU7+HorPdxet4/1do6V+QRce9T1P0cVha/n245f3P59nb+XKKHywHAueU/x88wWW9i+J7dS/Fj7D/UfZhGHEsxegPTcHIUBJJUsNFxFUUIyFuWMf7ZlJ0PtyrPLufzjK9CDgnM9foo6DJMaBLktQANrlLktQABnRJkhrAgC5JUgMY0CVJaoD1qy7AVMydOzd32GGHqoshSVLXLF68+L7MXOMiXrUO6DvssAODg4NVF0OSpK6JiNGXbgZscpckqREM6JIkNYABXZKkBqh1Dl2S1L7Vq1ezbNkyHnvssaqLojFstNFGbLvttmywwQYTer8BXZL61LJly5g9ezY77LADxV1x1SsykxUrVrBs2TJ23HHHCc1jk7sk9anHHnuMzTff3GDegyKCzTfffFKtJ9MW0CPiaxFxb0Tc2DJts4j4cUTcVj7OaXnttIi4PSJuXcu9oiVJHWQw712T3TbTeYZ+AcV9tFudClyRmTsDV5TPiYjdKe7VvEc5z5cjYr1pLJskqc9cffXV3HXXXdx0003ceOON656hDT//+c+5++67ueqqq1i2bNm0fMZ4pi2gZ+bPgftHTT4SuLD8/0LgdS3Tv5GZj2fm74DbgT+drrJJkurp7LPP5p//+Z8BOOSQQ8a8uNgFF1zAySefvMb7d9llF9773vdy+umns9NOO034M5csWcL3v//9Cb1333335aSTTuLSSy9l2223BYqLoN13330T/rx2dbtT3JaZuRwgM5dHxBbl9G2Aa1vet6yctoaIeCfwToDttttuGosqSeo1J554YtvvnzdvHieccAKbbLIJG2200YSXsWTJEgYHB3nNa16zzvfOnj2b73znO5MqY6f0Sqe4sRIFOdYbM/OczBzIzIF589a4lK0kqSbuuOMOdtttN+bPn88ee+zBYYcdxqOPPgrAueeey/7778/ee+/NUUcdxR//+EcAPvKRj/CZz3zm6WVcdNFFHHjggey5555cf/31a3zGyPvvvvtu9tlnH0477TTe9a53sd5667F06VKGhoY46qij2H///dl///25+uqrnzX/E088wYc+9CEuvfRS9tlnHy699FKuv/56DjzwQPbdd18OPPBAbr31VgCeeuopPvCBD/CiF72Ivfbaiy9+8YvPWtajjz7Kq171Ks4991xWrVrFO97xDvbff3/23Xdfvve97025Prsd0O+JiK0Aysd7y+nLgOe3vG9b4O4ul02StC4LF8LJJxePHXDbbbdx0kkncdNNN7Hpppty2WWXAfD617+eRYsW8atf/YrddtuN8847b8z5V61axTXXXMOXv/xl3vGOd4z7OVtvvTVLlixhyZIlzJ8/n6OOOortt9+e97znPbzvfe9j0aJFXHbZZZxwwgnPmm/mzJmceeaZvOlNb2LJkiW86U1v4oUvfCE///nPueGGGzjzzDM5/fTTATjnnHP43e9+xw033MCvf/1rjj322KeX88gjj/Da176WN7/5zcyfP5+Pf/zjvOIVr2DRokX87Gc/42//9m9ZtWrVlOqy203uC4HjgLPKx++1TL8kIj4LbA3sDKz5U0uSVJ2FC+GYY+CPf4Tzz4cFC+CII6a0yB133JF99tkHgP3224877rgDgBtvvJEPfvCDPPjggzzyyCO88pVjD3465phjADj44IN5+OGHefDBB9f6eVdffTVf/epX+cUvfgHAT37yE26++eanX3/44YdZuXIls2fPHncZDz30EMcddxy33XYbEcHq1aufXtaJJ57I+usXoXWzzTZ7ep4jjzySU0455ekgf/nll7Nw4cKnWxsee+wx7rzzTnbbbbe1ln9tpi2gR8QC4BBgbkQsAz5MEci/GRHHA3cCbwDIzJsi4pvAzcCTwEmZ+dR0lU2S1IbLLy+CORSPl18+5YC+4YYbPv3/euut93ST+9ve9ja++93vsvfee3PBBRdw5ZVXjjn/6KFdaxvqtXz5co4//ngWLlzIrFmzABgeHuY//uM/eM5znjPhMp9xxhm8/OUv5zvf+Q533HEHhxxyCFBcDGa8zz/ooIP4wQ9+wJvf/GYigszksssuY9ddd53w567LdPZyPyYzt8rMDTJz28w8LzNXZOahmblz+Xh/y/s/npl/kpm7ZuYPpqtckqQ2HXYYbLxx8f/GGxfPp8nKlSvZaqutWL16NRdffPG477v00ksBuOqqq9hkk03YZJNNxnzf6tWreeMb38inPvUpdtlll6enH3bYYXzpS196+vmSJUvWmHf27NmsXLny6ecPPfQQ22xT9Nu+4IILnrWss88+myeffBKA++9/ZqDXmWeeyeabb8673vUuAF75ylfyxS9+kcyiu9gNN9ww7jpOVK90ipMk9bojjiia2U86qSPN7WvzsY99jJe85CX85V/+JS984Quf9VrrWfCcOXM48MADOfHEE8fNswNcc801LFq0iA9/+MPss88+7LPPPtx999184QtfYHBwkL322ovdd9+ds88+e415X/7yl3PzzTc/3SnulFNO4bTTTuOggw7iqaeeaUw+4YQT2G677dhrr73Ye++9ueSSS561nM997nM89thjnHLKKZxxxhmsXr2avfbaiz333JMzzjij3ap6pl5Gfh3U0cDAQI41BlH9YXg4WbHqCebOmunVrqQ23HLLLVPK2Vbh3e9+Ny9+8Yt5+9vfXnVRumKsbRQRizNzYPR7PUNXLQ0PJ8ecey0v/eQVHH3OtQwP1/eHqaSJOeOMM7juuus4YhpbBurMgK5aWrHqCRYvfYAnh5PFSx9gxaonqi6SpGn2sY99jOuvv57NN9+86qL0JAO6amnurJnst/0c1p8R7Lf9HObOmll1kaRaqnPatekmu228H7pqKSJYMP8Ac+iyL8UUbLTRRqxYscJbqPagkfuhT+YStQZ01daMGcG82Ruu+41qrJG+FIuXPsB+289hwfwDmDHDwDRR2267LcuWLWNoaKjqomgMG2200dM3eJkIA7qk2hqrL4U/8iZugw02YMcdd6y6GOoQc+iSasu+FNIzPEOXVFv2pZCeYUCXVGv2pZAKNrlLktQABnRJkhrAgC5JUgMY0CVJagADuiRJDWBAlySpAQzoktSDhoeToZWPe/MUTZjj0CWpx3iNerXDM3RJ6jFjXaNeWhcDuiT1GK9Rr3bY5C5JPcZr1K/b8HBaP6MY0CWpB3mN+vHZx2BsNrlLkmrFPgZjM6BLkmrFPgZjs8ldklQr9jEYm2fo6ggvgiFpPNNxfBjpY2Awf4Zn6JoyO6hIGo/Hh+7xDF1TZgcVSePx+NA9BnRNmR1UJI3H40P3RJ1zngMDAzk4OFh1MYQXeZA0Po8PnRURizNzYPR0c+jqCC+CIWk8Hh+6wyZ3SZIawIAuSVIDGNClSerXMfcTWe9+rRtNL/eriTGHLk1Cv46pnch692vdaHq5X02cZ+jSJPTrmNqJrHe/1o2ml/vVxBnQpUno1zG1E1nvfq0bTS/3q4lzHLo0Sf06pvbJJ4e5fegRdtlyFjNmjH0u0K91o+nlfvVsjkOXOqQfx9QODyfHnnfdOvOY/Vg3mn7uVxNjk7ukdTKPKfU+A7qkdTKPKfU+m9wlrVNEsGD+AR3PY5oblTrHgC5pQjqdx3R8sdRZNrlLqoR5eamzDOiSKmFeXuosm9wrVtccYl3Lrd4xXXl5qV8Z0CtU1xxiXcut3uP4YqlzbHKvUF1ziHUttyQ1mQG9QnXNIda13JLUZF7LvWJ1zUXXtdySVHdey71H1TWHWNdyS1JT2eQuSVIDGNAlSWoAA7okSQ1gQJckqQEM6JIkNYABXZKkBjCgS5LUAAZ0SepBw8PJ0MrHqfPFv9RdXlhGknqMN0BSOzxDl6Qe4w2Q1A4DuiT1GG+ApHbY5C5JPSYiWDD/AG+ApEkxoEtSD/IGSJosm9wlSWoAA7okSQ1gQJfUNY6tlqaPOXRJXeHYaml6eYYuqSscWy1NLwO6pK5wbLU0vWxyl9QVjq2WppcBXVLXOLZamj42uUuS1ACVBPSIeF9E3BQRN0bEgojYKCI2i4gfR8Rt5eOcKsomSVIddT2gR8Q2wN8AA5m5J7AecDRwKnBFZu4MXFE+lyRJE1BVk/v6wHMiYn1gY+Bu4EjgwvL1C4HXVVM0SaqeF+HRZHU9oGfm74HPAHcCy4GHMvNyYMvMXF6+ZzmwRbfLJkm9YOQiPC/95BUcfc61DA8b1LVuVTS5z6E4G98R2Bp4bkS8ZRLzvzMiBiNicGhoaLqKKUmV8SI8akcVTe5/AfwuM4cyczXwbeBA4J6I2AqgfLx3rJkz85zMHMjMgXnz5nWt0JLULV6ER+2oYhz6ncABEbEx8ChwKDAIrAKOA84qH79XQdkkqXJehEft6HpAz8zrIuJbwC+BJ4EbgHOAWcA3I+J4iqD/hm6XTZJ6hRfh0WRVcqW4zPww8OFRkx+nOFuXJEmT5JXiJElqAAO6JEkNYECXJKkBDOiSJDWAAV2SpAYwoEuS1AAGdEmSGsCALklSAxjQJUlqAAO61AO897Wkqark0q+SnjFy7+vFSx9gv+3nsGD+AcyY4c04JE2OZ+hSxbz3taROMKBLFfPe15I6wSZ3dcTwcHrv5jb16r2v3aZSvRjQNWXmgKeu1+597TaV6scmd02ZOeDmcZtK9WNA15SZA24et6lUP1Hnca8DAwM5ODhYdTGE+dYmcptKvSkiFmfmwOjpnqGrI0ZywB74u6MbF6Jxm0r1Yqc4qWbssCZpLJ6hSzVjhzVJYzGgSzVjhzVJY7HJXaqZXr0QjaRqGdClGuq1C9FIqp5N7pIkNYABXZKkBjCg96FujGGuK+tGUl2ZQ+8zjmEen3Ujqc48Q+8zjmEen3Ujqc4M6H3GMczjs24k1Zk3Z+lD3nRjfNaNpBG9ejwY7+Ys5tD7kGOYx2fdSIJ69qmxyV2SpFHq2KfGgC5J0ih17FNjk7ukjunVnKMK/bx9JrvudbxnggFdUkfUMefYT/p5+7S77nXrU2OTu6SOqGPOsZ/08/bpl3U3oEvqiDrmHPtJP2+ffll3x6FLXdbkPGYV69bk+hxtquvaT3U1WpPW3XHoUg9oeh6z2znHptdnq06sa91ywp3UD+tuk7vURf2Sy+uWfqrPflpXtceALnVRv+TyuqWf6rOf1lXtMYcudVmTcnm9oJ/qs5/WVeMbL4fuGXqPGx5OhlY+Tp1/eOnZRnJ5HpA7Yzrqs1e/d+473dWr+8F47BTXw/qpw4/UK/zeCeq5H3iG3sPsBCN1n987QT33AwN6D7MTjNR9fu8E9dwP7BTX4+wEI3A/6DbrW9C7+4EXlqmpfrgYgtaujrm8uvN7J6jffmCTu9Tj6pjLk9R9BnSpx9Uxlyep+2xyl3pcRLBg/gE9mcuTpkOv5q57nQFdqoG65fKkdtlnpH02uUuSeoZ9RtpnQJck9Qz7jLTPJndJUs+wz0j7DOiSpJ5in5H22OQuSVIDGNAlSWoAA7p6Vt3uRSxJVTKHrp7kWFRJmhzP0NWTHIsqSZNjQFdPciyqJE2OTe7qSY5FlfqX13JvjwFdPcuxqFL/sf9M+2xylyT1DPvPtM+ALknqGfafaZ9N7pKknmH/mfYZ0CVJPcX+M+2xyV2SpAYwoEuS1AAGdEmSGsCALklSAxjQJUlqgEoCekRsGhHfiojfRMQtEfHSiNgsIn4cEbeVj3OqKJskSXVU1Rn654EfZuYLgb2BW4BTgSsyc2fgivK5JEmagK4H9Ih4HnAwcB5AZj6RmQ8CRwIXlm+7EHhdt8smSVJdVXGG/gJgCDg/Im6IiK9GxHOBLTNzOUD5uEUFZZMkqZaqCOjrAy8G/ikz9wVWMYnm9Yh4Z0QMRsTg0NDQdJVRkqRaqSKgLwOWZeZ15fNvUQT4eyJiK4Dy8d6xZs7MczJzIDMH5s2b15UCS5LU67oe0DPzD8BdEbFrOelQ4GZgIXBcOe044HvdLpvqb3g4GVr5OJlZdVHUw9xP1ERV3Zzl3cDFETET+C3wdoofF9+MiOOBO4E3VFQ21dTwcHLMudeyeOkD7Lf9HBbMP4AZM7xTk57N/URNVUlAz8wlwMAYLx3a5aKoQVaseoLFSx/gyeFk8dIHWLHqCe/YpDW4n6ipvFKcGmPurJnst/0c1p8R7Lf9HObOmll1kdSD3E/UVFHnHNLAwEAODg5WXQxNwPBwsmLVE8ydNZOI6Wve7NbndFpdy11X1rfqLCIWZ+YardxV5dDVR7qZs5wxI2rXfGpOt/vquJ9I62KTu6bdWDlLPcP6kdQJBnRNO3OWa2f9SOoEc+jqCnOWa2f9SJooc+iqlDnLtbN+JE2VTe6SJDWAAV2SpAYwoKs2vP5273MbSdUxh65acKx273MbSdXyDF214Fjt3uc2kqplQFctOFa797mNpGo5Dl214Vjt3uc2kqbfeOPQPUNvgoUL4eSTi8cGGxmrXXWgsOPX+Ca7jaxLqXPsFFd3CxfCMcfAH/8I558PCxbAEUdUXarGsuNX51iXUmd5hl53l19eBHMoHi+/vNryNJwdvzrHupQ6y4Bed4cdBhtvXPy/8cbFc00bO351jnUpdZad4ppg4cLizPyww4rm9tHP1VF2/Ooc61LTZfS+1aR9bbxOcQb0pmnNqW+8sTl1SX1ndP+Mi49/Cceed11j+mvYy71fmFOX1OdG98+4feiRvuivYUBvGnPqkvrc6P4Zu2w5qy/6a9jk3kTm0CX1uSefHOb2oUfYZctZzJgxY1py6FXl5cdrcnccehMdcYSBXFLfGh7OMXPm82Zv2NHP6LXrKNjkLklqlG5c46AXr6NgQJckNUo3rnHQi9dRMIcuTVKTxrNKTdWN76k5dKnGejFvJmlNnc6ZV/UZk2GTuzQJvZg3kyQwoEuT0ot5M0kCm9zVMNOd04oIFsw/wBy6pJ5jQFdjdCu/3Wt5M0kCm9zVIOa3JfWzdQb0iDg5IuZ0ozDSVJjfltTPJtLk/t+ARRHxS+BrwI+yzoPX1Vjmt6XO87oL9bHOM/TM/CCwM3Ae8Dbgtoj4RET8yTSXTZq0kfy2Bx5p6kb6pbz0k1dw9DnXMjzsuVwvm1AOvTwj/0P59yQwB/hWRHx6GssmSaqQ/VLqZSI59L+JiMXAp4GrgRdl5v8A9gOOmubySZIqYr+UeplIDn0u8PrMXNo6MTOHI+Lw6SmWJKlq9kupl3UG9Mz80Fpeu6WzxZEk9RKvu1AfjkOXJKkBDOiSJDWAAV2SpAYwoLcYHk6GVj6O182RJNWNN2cpdevGHpIkTQfP0EteQEGSVGcG9JIXUJAk1ZlN7iUvoLB23qBBUr+p23HPgN7CCyiMzf4FkvpNHY97NrlrnexfIKnf1PG4Z0DXOtm/QFK/qeNxL+o85npgYCAHBwerLkZfWFcuqW65pm6ybqTeM5HvZa8e9yJicWYOjJ5uDl0Tsrb+BXXMNXWLdSP1nol+L+t23LPJXVNWx1xTt1g3Uu/pxPeyF7/bBnRNWR1zTd1i3Ui9pxPfy178bptDV1tG547ME4/PupF6Tye+l+bQVXvj5Y4cwz8260bqPZ34Xvbad9smd01aL+aOJKnfGdA1ab2YO5KkfmeTuybN695LUu8xoKstvZY7kqR+Z5O7JEkNYECXJKkBDOiSJDWAAV2SpAYwoEuS1AAGdEmSGsCALklSAxjQJakHDQ8nQysfp8430FJ3eWEZSeox490ASVobz9Alqcd4AyS1w4AuST3GGyCpHTa5S1KP8QZIvWF4OKe0DaY6/2QZ0CWpB3kDpGpNtR9DFf0gKmtyj4j1IuKGiPjX8vlmEfHjiLitfJxTVdkkSf1tqv0YqugHUWUO/T3ALS3PTwWuyMydgSvK55Ikdd1U+zFU0Q8iqhjjGBHbAhcCHwf+Z2YeHhG3Aodk5vKI2Aq4MjN3XdtyBgYGcnBwsAslluqv2/k8qe56NYceEYszc2D09Kpy6J8DTgFmt0zbMjOXA5RBfYsqCiY1keOapcmbaj+GbveD6HqTe0QcDtybmYvbnP+dETEYEYNDQ0MdLp3UTI5rlpqvihz6QcAREXEH8A3gFRFxEXBP2dRO+XjvWDNn5jmZOZCZA/PmzetWmaVac1yz1HyV5NCf/vCIQ4APlDn0/x9YkZlnRcSpwGaZecra5q9DDt28ZedYl1Nj/UnN0Gs59LGcBXwzIo4H7gTeUHF5psy8ZedYl1PnuGap2SoN6Jl5JXBl+f8K4NAqy9NpY+UtPaC2x7qUpLXzWu7TyLxl51iXkrR2lebQp8ocen+xLiWpHjn0RjJv2TnWpSSNzyZ3SZIawIAuSVIDGNAlSWoAA7qkaTM8nAytfJw6d76V6sJOcZKmhRcDkrrLM3RJ08IbwkjdZUCXNC28GJDUXTa5S5oWEcGC+Qd4MSCpSwzokqaNFwOSuscmd0mSGsCALklSAxjQp6ApY2ybsh6S1M/MobepKWNsm7IektTvPENvU1PG2DZlPSSp3xnQ29SUMbZNWQ9J6ndR57zpwMBADg4OVvb5w8M55TG2nVjGVPVCGSRJExMRizNzYPR0c+hTMNUxtr2Sv3assCTVn03uFTJ/LUnqFAN6hcxfS5I6xSb3CvXyta7Nq6sq7nvdZX03hwG9Yr2Yv+6V3L76j/ted1nfzWKTu9Zgbl9Vcd/rLuu7WQzoWoO5fVXFfa+7rO9mcRy6xmReTVVx3+uuptZ3U9cLHIeuSerF3L76g/tedzWxvvu1b4BN7pKkRunXvgEGdElSo/Rr3wCb3CVJjdLL1/iYTp6hqyuGh5OhlY9T506YkupjpG9AvwRz8AxdXdCvHVQkqZs8Q9e069cOKpLUTQZ0Tbt+7aAiSd1kk7umXb92UJHULL1+sRoDurqiiRevkNQ/6tAXyCZ3SZLWoQ59gQzokiStQx36AtnkLknSOtShL5ABXZKkCej1vkA2uUuS1AAGdEmSGsCALkmjeO8B1ZE5dElqUYfxxtJYPEOXpBZ1GG8sjcWALkkt6jDeWBqLTe6S2tbr17ZuRx3GG0tjMaBLakuTc829Pt5YGotN7pLaYq5Z6i0GdEltMdcs9Rab3CW1pRO55rrk4NspZ13WTc1hQJfUtqnkmuuSg2+nnHVZNzWLTe6SKlGXHHw75azLuqlZDOiSKlGXHHw75azLuqlZos7XKh4YGMjBwcGqiyGpTXXJM5tDVy+JiMWZOTB6ujl0SZWpy3jvdspZl3VTc9jkLklSAxjQJUlqAAO6JEkNYECXJKkBDOiSJDWAAV2SpAYwoEuS1AAGdEmSGsCALklSAxjQJUlqAAO6JEkNYECXJKkBDOiSJDWAAV2SpAYwoEuS1AAG9IoNDydDKx8nMytdRlNYF5L61fpVF6CfDQ8nx5x7LYuXPsB+289hwfwDmDEjur6MprAuJPUzz9ArtGLVEyxe+gBPDieLlz7AilVPVLKMprAuJPWzrgf0iHh+RPwsIm6JiJsi4j3l9M0i4scRcVv5OKfbZeu2ubNmst/2c1h/RrDf9nOYO2tmJctoCutCUj+LbucaI2IrYKvM/GVEzAYWA68D3gbcn5lnRcSpwJzM/F9rW9bAwEAODg5OW1mHh5MVq55g7qyZRExP020nPqMb5awL60LtcL9RnUTE4swcGD296zn0zFwOLC//XxkRtwDbAEcCh5RvuxC4ElhrQJ9O3crHzpgRzJu9YeXLaArrQpNl3ws1RaU59IjYAdgXuA7Ysgz2I0F/i3HmeWdEDEbE4NDQ0LSVzXys1B/8rqspKgvoETELuAx4b2Y+PNH5MvOczBzIzIF58+ZNW/nMx0r9we+6mqKSYWsRsQFFML84M79dTr4nIrbKzOVlnv3eKso2IiJYMP8A82pSw/ldV1NU0cs9gPOAWzLzsy0vLQSOK/8/Dvhet8s22kg+1i+41Gx+19UEVZyhHwS8FfjPiFhSTjsdOAv4ZkQcD9wJvKGCskmSVEtV9HK/ChjvZ/Ch3SyLJElN4ZXiJElqAAO6JEkNYECXJKkBDOiSJDWAAV2SpAYwoGtaDA8nQysfp9s3/5GkiWjiMaqSK8Wp2bzZhaRe1tRjlGfo6jhvdiGplzX1GGVAV8d5swtJvaypx6ioc/5gYGAgBwcHqy6GxjA8nN7sQlLP6sYxaro+IyIWZ+bA6Onm0DUtRm52IUm9aLqPUVXk6W1ylySpw6rI0xvQJUnqsCry9Da5S5Iq1cQ+NxHBgvkHdHW9DOiSpMo0dUw4dL8vkU3ukqTKNHVMeBUM6JKkyjR1THgVbHKXJFWmilxzUxnQJUmV8roVnWGTuyRJDWBAlySpAQzoktrWxHtK9zLrW2tjDl1SW5o8frgXWd9aF8/QJbXF8cPdZX1rXQzoktri+OHusr61Lt4PXVLbmngN7l5mfQvGvx+6Z+gN1C8dZ/plPXvZyPhhg0t3WN9aGzvFNUy/dJzpl/WUpInyDL1h+qXjTL+spyRNlAG9Yfql40y/rKckTZSd4hqoXzrO9Mt6SlKr8TrFmUNvoH650UG/rKckTYRN7pIkNYABXZKkBjCgS5LUAAZ0SZIawIAuSVIDGNAlSWoAA7okSQ1gQJckqQEM6JIkNYABXZKkBjCgS2vhPdcF7geqB6/lLo3De64L3A9UH56hS+PwnusC9wPVhwFdGof3XBe4H6g+vB96zXgP8O6yvgXuB+ot3g+9AczldZ/3XBe4H6gebHKvEXN5kqTxGNBrxFyeJGk8NrnXSESwYP4B5vIkSWswoNeMuTxJ0lhscpckqQEM6JIkNYABXZKkBjCga1p4MwtJ6i47xanjvACOJHWfZ+jqOC+AI0ndZ0BXx3kBHEnqPpvc1XG9fAEcb7IhqakM6JoWvXgBHHP7kprMJnf1DXP7kprMgK6+YW5fUpPZ5K5GWVuOvJdz+5I0VQZ0NcZEcuS9mNuXpE6wyV2NYY5cUj8zoKsxzJFL6mc2uasxzJFL6mcGdDWKOXJJ/comd0mSGsCALklSAxjQJUlqAAO6JEkNYECXJKkBei6gR8SrIuLWiLg9Ik6tujySJNVBTwX0iFgP+Efg1cDuwDERsXu1pZIkqff1VEAH/hS4PTN/m5lPAN8Ajqy4TJIk9bxeC+jbAHe1PF9WTpMkSWvRawF9rGt15rPeEPHOiBiMiMGhoaEuFUuSpN7WawF9GfD8lufbAne3viEzz8nMgcwcmDdvXlcLJ0lSr+q1gL4I2DkidoyImcDRwMKKyyRJUs/rqZuzZOaTEXEy8CNgPeBrmXlTxcWSJKnn9VRAB8jM7wPfr7ockiTVSa81uUuSpDYY0CVJaoDIzHW/q0dFxBCwdAqLmAvc16HiyPrsNOuzc6zLzrI+O2uy9bl9Zq4xzKvWAX2qImIwMweqLkdTWJ+dZX12jnXZWdZnZ3WqPm1ylySpAQzokiQ1QL8H9HOqLkDDWJ+dZX12jnXZWdZnZ3WkPvs6hy5JUlP0+xm6JEmN0LcBPSJeFRG3RsTtEXFq1eWpk4h4fkT8LCJuiYibIuI95fTNIuLHEXFb+Tin6rLWSUSsFxE3RMS/ls+tzzZFxKYR8a2I+E25n77U+mxPRLyv/J7fGBELImIj63LiIuJrEXFvRNzYMm3c+ouI08q4dGtEvHIyn9WXAT0i1gP+EXg1sDtwTETsXm2pauVJ4P2ZuRtwAHBSWX+nAldk5s7AFeVzTdx7gFtanluf7fs88MPMfCGwN0W9Wp+TFBHbAH8DDGTmnhT32Dga63IyLgBeNWramPVXHkePBvYo5/lyGa8mpC8DOvCnwO2Z+dvMfAL4BnBkxWWqjcxcnpm/LP9fSXGw3IaiDi8s33Yh8LpKClhDEbEt8FfAV1smW59tiIjnAQcD5wFk5hOZ+SDWZ7vWB54TEesDG1Pc0tq6nKDM/Dlw/6jJ49XfkcA3MvPxzPwdcDtFvJqQfg3o2wB3tTxfVk7TJEXEDsC+wHXAlpm5HIqgD2xRYdHq5nPAKcBwyzTrsz0vAIaA88sUxlcj4rlYn5OWmb8HPgPcCSwHHsrMy7Eup2q8+ptSbOrXgB5jTLO7/yRFxCzgMuC9mflw1eWpq4g4HLg3MxdXXZaGWB94MfBPmbkvsAqbhNtS5naPBHYEtgaeGxFvqbZUjTal2NSvAX0Z8PyW59tSNCNpgiJiA4pgfnFmfrucfE9EbFW+vhVwb1Xlq5mDgCMi4g6K9M8rIuIirM92LQOWZeZ15fNvUQR463Py/gL4XWYOZeZq4NvAgViXUzVe/U0pNvVrQF8E7BwRO0bETIpOCAsrLlNtRERQ5CdvyczPtry0EDiu/P844HvdLlsdZeZpmbltZu5AsS/+NDPfgvXZlsz8A3BXROxaTjoUuBnrsx13AgdExMbl9/5Qij4z1uXUjFd/C4GjI2LDiNgR2Bm4fqIL7dsLy0TEayjylusBX8vMj1dbovqIiD8DfgH8J8/kfE+nyKN/E9iO4kDwhswc3RlEaxERhwAfyMzDI2JzrM+2RMQ+FB0MZwK/Bd5OcQJjfU5SRHwUeBPF6JYbgBOAWViXExIRC4BDKO6odg/wYeC7jFN/EfF3wDso6vu9mfmDCX9WvwZ0SZKapF+b3CVJahQDuiRJDWBAlySpAQzokiQ1gAFdkqQGMKBLktQABnRJkhrAgC5pwiJi/4j4dXlP7OeW98nes+pySfLCMpImKSL+HtgIeA7FNdM/WXGRJGFAlzRJ5f0PFgGPAQdm5lMVF0kSNrlLmrzNKK7lPZviTF1SD/AMXdKkRMRCitu87ghslZknV1wkScD6VRdAUn1ExF8DT2bmJRGxHnBNRLwiM39addmkfucZuiRJDWAOXZKkBjCgS5LUAAZ0SZIawIAuSVIDGNAlSWoAA7okSQ1gQJckqQEM6JIkNcD/AwN5pv/JI1CXAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "tacke = plotovanje_tacaka_najkrace_duzi(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4750963f",
   "metadata": {},
   "source": [
    "### Optimizacija"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "bc0797d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def distance(p1,p2):\n",
    "    xdiff = p1[0]-p2[0]\n",
    "    ydiff=p1[0]-p2[0]\n",
    "    return (xdiff**2+ydiff**2)**0.5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "9f99e93a",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bruteforce(points):\n",
    "    return min(\n",
    "        (distance(*pairing), pairing)\n",
    "        for pairing in combinations(points,2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "c41cd6d4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def mindistance(tacke):\n",
    "    duzina = len(tacke)\n",
    "    if duzina <5:\n",
    "        return bruteforce(tacke)\n",
    "    \n",
    "    leve_tacke = tacke[:duzina//2]\n",
    "    desne_tacke = tacke[duzina//2:]\n",
    "    \n",
    "    najkraca_u_levim = mindistance(leve_tacke)\n",
    "    najkraca_u_desnim = mindistance(desne_tacke)\n",
    "    \n",
    "#     print(40*'==')\n",
    "    \n",
    "#     print('najkraca_u_levim:', najkraca_u_levim)\n",
    "#     print('najkraca_u_desnim:', najkraca_u_desnim)\n",
    "    \n",
    "    d = min(najkraca_u_levim, najkraca_u_desnim)[0]\n",
    "    \n",
    "#     print('d', min(najkraca_u_levim, najkraca_u_desnim), 'd[0]', d)\n",
    "    \n",
    "#     print(40*'==')\n",
    "    \n",
    "    limit_right=[tacka for tacka in desne_tacke if abs(tacka[0]- desne_tacke[0][0]) <= d]\n",
    "    \n",
    "    limit_left= [tacka for tacka in leve_tacke if abs(tacka[0] - leve_tacke[-1][0])<=d]\n",
    "   \n",
    "    distances =[najkraca_u_levim, najkraca_u_desnim]\n",
    "    for x in limit_left:\n",
    "        for y in limit_right:\n",
    "            distances.append((distance(x,y), (x,y)))\n",
    "    return min(distances)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "8107bb75",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "potrebno vreme za brute force: 0.022 sekunde\n"
     ]
    }
   ],
   "source": [
    "import time\n",
    "start = time.monotonic()\n",
    "sve_duzi = povuci_sve_duzi(tacke)\n",
    "najkraca_duz1 = izracunaj_najkracu_duz(sve_duzi)\n",
    "end = time.monotonic()\n",
    "print('potrebno vreme za brute force:', round(end-start,3), 'sekunde')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "1ff45368",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "potrebno vreme za optimizovani search: 0.0022 sekunde\n"
     ]
    }
   ],
   "source": [
    "start = time.monotonic()\n",
    "najkraca_optimizovana = mindistance(tacke)\n",
    "end = time.monotonic()\n",
    "print('potrebno vreme za optimizovani search:', round(end-start,4), 'sekunde')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}