MonotoneChainConvexHull.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "MonotoneChainConvexHull.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "BPLo5BE7COIf",
        "colab_type": "text"
      },
      "source": [
        "##Monotone Chain Convex Hull\n",
        "\n",
        "---\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FKeVYJ77lB4N",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def cross(q,p,r):\n",
        "  return (p[0] - q[0]) * (r[1] - q[1]) - (p[1] - q[1]) * (r[0] - q[0])"
      ],
      "execution_count": 94,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "LjxcMDpIzQf8",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def ConvexHull(v):\n",
        "\n",
        "    v = sorted(set(v))\n",
        "\n",
        "    Llower = []\n",
        "    for p in v:\n",
        "        while len(Llower) >= 2 and cross(Llower[-2], Llower[-1], p) <= 0:\n",
        "            Llower.pop()\n",
        "        Llower.append(p)\n",
        "\n",
        "    Lupper = []\n",
        "\n",
        "    v = reversed(v)\n",
        "    for p in v:\n",
        "        while len(Lupper) >= 2 and cross(Lupper[-2], Lupper[-1], p) <= 0:\n",
        "            Lupper.pop()\n",
        "        Lupper.append(p)\n",
        "\n",
        "    return Llower[:-1] + Lupper[:-1]\n"
      ],
      "execution_count": 95,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "W4q-qpjwz07v",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from random import seed\n",
        "from random import randint\n",
        "seed(1)"
      ],
      "execution_count": 96,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "SGhvQ5hP0CgC",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "n = 100\n",
        "v = []\n",
        "for i in range(100):\n",
        "  x = randint(0,200)\n",
        "  y = randint(0,200)\n",
        "  v.append((x,y))"
      ],
      "execution_count": 97,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "EtfwozJl0M5C",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "import matplotlib.pyplot as plt\n",
        "import numpy as np"
      ],
      "execution_count": 98,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ADpR_81D0wX3",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "ans = ConvexHull(v)\n",
        "xyz = np.array(v)"
      ],
      "execution_count": 99,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "PG87z6zE1LAb",
        "colab_type": "code",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 264
        },
        "outputId": "2a9dd8f0-584d-4d98-cb45-f44113229918"
      },
      "source": [
        "fig, ax = plt.subplots()\n",
        "ax.scatter(xyz[:,0], xyz[:,1])\n",
        "for i in range(len(ans)):\n",
        "  x = [ans[i][0], ans[(i+1)%len(ans)][0]]\n",
        "  y = [ans[i][1], ans[(i+1)%len(ans)][1]]\n",
        "  ax.plot(x,y, 'gray', linestyle='-', marker='')"
      ],
      "execution_count": 100,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjIsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+WH4yJAAAgAElEQVR4nO2df5Bc1XXnP6d/zA9pRhJCQpLHGjSATAwyIHvWdizbZWM7AmwDxluO2VSCE+8q3rJr7STrRNipmE3iWAnB3mSTJSsH1vaWjX8UIFhDYoixF4cKtiUEEgJkEAikQUgyoG6NNJrpnj77R7+Wekbd07/ej/ten09V13Tffj19+r77zjv3e8+9V1QVwzAMI1mkojbAMAzD8B9z7oZhGAnEnLthGEYCMeduGIaRQMy5G4ZhJJBM1AYALFmyRFetWhW1GYZhGLFi27Ztv1TVpbXec8K5r1q1iq1bt0ZthmEYRqwQkefrvWeyjGEYRgIx524YhpFAzLkbhmEkEHPuhmEYCaShcxeRlSLyIxF5QkR2icinvfLFInK/iDzt/T3DKxcR+VsReUZEdojIG4P+EYZhGMZMmonci8AfqOoFwFuBT4rIBcBG4Iequhr4ofca4HJgtffYANzsu9WGYTRky/Yx1m16gJGN97Bu0wNs2T4WtUlGiDRMhVTVA8AB7/lREXkSGAKuAt7lHfZ14MfAH3nl39DycpMPi8giEVnh/R/DMEJgy/Yxrr9jJxOFaQDGjkxw/R07Abh67VCUpjnDlu1j3PiD3bx4ZILXLOrns+vPT1TdtJTnLiKrgLXAT4FlVQ77JWCZ93wI2Ff1sf1e2QznLiIbKEf2DA8Pt2i2YXQv09PTTE1NUSgU6v697d6dnKuTrMjmKZDiVZ1HSYXv3XOIZSdWk0qlEBFSqdTJR6PX7Xym3v8QkUjrsBtufk07dxEZAG4HPqOq+eqTo6oqIi0tDK+qm4HNAKOjo7aovJEYVJVCoVDT6c7lkJs5plAoUCqVGtpwAUD21OsRjpSfTMN99z0XyO9uhYqD9+NG0czr2eV3bd3PhTrN0p6jHC4NsHt6KUcLvdz4g93d5dxFJEvZsX9TVe/wig9W5BYRWQEc8srHgJVVH3+tV2YYzlAqlRo62bmcbqPjWiWbzdLT03Pa3/7+/pOv6x1T670P/6+fsT83RZEUCgiQQhla2Md9v/cOVJVSqXTy0eh1M8fM9Xrn/iM8uPsQR09MsbAvw6+eu5jVS+fX/Uwr9hSLxZbtGSoWSGWUFMry9DHekD3Icc1w6PgA//Zv/QwPD7N8+XLS6bTvbS8sGjp3KYfotwBPquqXq966G7gO2OT9vauq/FMi8m3gLUDO9PZ44JIGqaoUi8Wmo91mot/q59PT0y3Zk0qlajrWvr4+BgcHm3LA9f5mMpmWZYpG5+rTl72B6+/YScGTHRToyWb4/csuoK+vr6Xv6pQt28f4yo4cE4Ul5YJx+PkTab50zesja1/rNj3A2JEJQFkkJ1iWGues1DivyRzjvvvuAyCTyTA0NMTw8DArV65k5cqVodddJ0ijbfZE5O3AT4CdQKU/+DnKuvt3gWHgeeAjqvqKdzP4O+Ay4Djw26o658Ixo6OjamvLRMtsDRKgP5vmS9e8oe4FWCqVOpIaGh3f6haQmUymoSNttmz2X5ciuGbPlSs361OOdCZDi/p5aOOlodsDc9fhe85bwAsvvMC+fft44YUXeOmll062xbPOOouVK1cyPDzM8PAwCxcunHFjDrvORWSbqo7WfM+FPVTNuUfPuk0PMJk7xFuy+xjXXqZJkZESA1kYXbmgpgMuFostfYeI+OZsax0b9SBdWLjoLOdiZOM91PIyAjy36f1hm3OSZh3x1NQUY2NjJx3+vn37mJqaAmBwcPBkZL/neB9//sCLHC+cGhNpFCB1ylzO3YlVIY3oGB8fZ+fOnbxpYhtn9h1HFc5ggknNUiRFsVieCjFv3jwWLVp0mkNtxRGn0+muccBB8mINxz5XedS8ZlF/zZvRaxb1R2DNKa5eO9SU0+3p6WFkZISRkRGg3GM9dOjQjOh+165dAFyTTpFP9TKlaR4qnM3RQn9kg7Tm3LuQQqHAU089xY4dO9izZw+qSiY9wE8nV/Ls9GJOVKVZDC3q53987FQ0uGX7GH9xMtpJ89n1qxKTXRAXXHWW9fjs+vNrSiCfXX9+hFa1TyqVYvny5Sxfvpw3v/nNAORyOT70V3dxVmqcVelXOTM1wb9P7+LA9CB7jp7J5OQkvb29odppzr1LUFX27t3Ljh07eOKJJ5iammLBggWsW7eOiy66iIf2T/FPd+zkxHT9C7AbcoPjQNycZaVtuKD/B8XChQuZHHwtDx+Z4OHC2QzKBOekX+W89Mu8vWcvN910E69//eu5+OKLGRkZQUQC1+dNc084hw4dYseOHezcuZN8Pk9PTw8XXHABF198MWeffXZLg0Fx03qTjCuDpa4RZb3UHqRN8cfvWsaC42Ps2rWLyclJFixYQN+yEf73k8qhQk/Vsa3r8zag2mVUdPQdO3bw0ksvISKcd955XHTRRZx//vlks9nG/6QGrg6MGQa0l/EVhA31bi6FQoHdu3fz2GOP8fQzzyDAeCnL/tJC/q2wCmg9ULIB1S6glo6+YsUK1q9fz5o1axgYGOj4O+Km9RruEEZEfeMPds9w7AAThelQBzTnGqTNZrOsWbOGNWvWcMHGOzkn8wpvzIyxInX05DF+Doqbc48xjXT0pUtr7pvbNnHTeg03aHasptMbQJyyiM5YtJDHj/RwfvoQL5fmnSz3M1Ay5x5DWtHR/aTZgTHTg41qmomo/Risj1PPshIoCVDyVl73O1Ay5x4T6uno73vf+zrS0VulUW6wZdQYs2kmovZDUolTz7Lymx6++1G0VNba/Q6CzLk7TBg6ut+4oHsabtFMRO2HpOJnymUYvc+r1w7x7I96eNt5w1x5pf/ZZubcHSNsHd1v4qR7GuHQTETtl6TS7KzTuQiz96mqgcmo5twdISod3W86vUhNr08ezUTULkkqYfY+S6WSOfckMj4+zuOPP86OHTs4cOBAZDq6n3RykZpen1waRdQuzWINs/epqqRSzWxl3Trm3EMmjjp6K3RykZpe3934Ian4QZhZNybLxJy46+it0u5Fanq94QJhSkQmy8SUw4cP89hjj8VeRw+LOOUpG8klTIkoUllGRG4FPgAcUtU1Xtl3gMptbBFwRFUvEZFVwJPAbu+9h1X1E34b7TJJ1NHDIqpBNRvENWYTlkQUtSzzNcrb5n2jyqBfrzwXkZuAXNXxe1T1Er8MjANJ19HDIopBNRvENaIkUllGVR/0IvLT8PZL/QjQdeu91tPR3/a2t3HxxRcnQkePIqINe1DNBnGNKHE5W+YdwEFVfbqqbEREtgN54I9V9Se1PigiG4ANAMPDwx2aER71dPSLLrqIVatWJUZH75aI1gZxjSiJWpaZi2uB26peHwCGVfVlEXkTsEVELlTV/OwPqupmYDOU13Pv0I5A6UYdvVsi2qQM4tq4Qfyo7KXhnHMXkQxwDfCmSpmqTgKT3vNtIrIHeB0Qu504ul1H75aI1qWZke3SLb2spFFx7i7KMu8FnlLV/ZUCEVkKvKKq0yJyDrAaeLZDG0OjG3T0ZklKRNuIoAdxu2WTCqN1SqUSEGHkLiK3Ae8ClojIfuALqnoL8FFmSjIA7wT+VEQKQAn4hKq+4q/J/tMtOnorJCGibZagBnHDiqi7pZeVNCKXZVT12jrlH6tRdjtwe+dmBU836uit4NJaH3ElrIi6W3pZScNlWcZpanWH37/mrK7W0VvFlbU+4kpYEXU39bKSROSyTByZ2R1WpvMHuXPLU+y89wilYqFrdXQjXMKKqK2XFU8il2XiSKU7/M7sHs5OHyEjypSm2FdayvW/tb5rdXQjXMKMqP3uZVlqZfCYLNMGlW7voEwB8OOpc3hheiEl0mweGYnSNKOLiGtEbamV4WCyTBtUusNFUryi83huejFQ3oTWaA6L3PwhjuMWlloZDkHLMsH0ByLms+vPpz+bZr5McazUA9gAUytUIrexIxMopyK3LdvHojbNCAFLrQwHc+5tcPXaIf7iQ2sYSBU4pj0MLernS9e8waKOJpkrcjOST70BX0ut9JeKLBOU5p5I5w6w/lcWk6bEH3zgEh7aeKk59hawyK27qfR8q7Ger/9Y5N4m+Xx5rbIFCxZEbEn8sMitu7l67RBfuuYNDC3qR8B6vgFhqZBtksuV9w9ZuHBhxJbED5sUY8RxIDhuBC3LJNa5W+TePnFN4TPiRzdnZVnk3ia5XI5UKmVLCrSJRW5G0HR7Pr1p7m2Sz+dZsGCBzUQ1DEfp9qwsy5Zpk4pzNwzDTbo9K8si9zbJ5XI2mGoYDtPtWVmmubeBqlrk3iHdPNBlBEulbY0dmUCA6g2UuykrK/JsGRG5FfgAcEhV13hlNwD/CTjsHfY5Vb3Xe+964OPANPBfVPUHAdg9J8eOHaNUKplzb5OgBrridMOIk61xYnbbUjjp4Ie6rJ5diNy/Bvwd8I1Z5V9R1b+uLhCRCyhvv3ch8BrgX0Tkdao6TYhYjntnBLFwVJwyI+Jka9yo1bYqjv2hjZdGY1RERK65q+qDQLP7oF4FfFtVJ1X1OeAZ4M0d2NcWluPeGUEMdMUpMyJOtsaNbh9ErcblbJlPicgOEblVRM7wyoaAfVXH7PfKTkNENojIVhHZevjw4VqHtI1F7p0RxEBXnC7qONkaN7p9ELWayCP3OtwMnAtcAhwAbmr1H6jqZlUdVdVRv7e6y+fzZDIZ+vu7r8H4QRALR8Xpoo6TrXHDFiU7hZPOXVUPquq0qpaAr3JKehkDVlYd+lqvLFTiNoFpy/Yx1m16gJGN97Bu0wORr5sexMJRcbqo42Rr3LBFyU4RebZMLURkhaoe8F5+CHjce3438C0R+TLlAdXVwM86trJF4pTj7urgnd/LD8RpvZo42RpHbGmLMpFny4jIbcC7gCUish/4AvAuEbmE8kD3XuB3PWN3ich3gSeAIvDJsDNloBy5j8Rkr9Ru2tIsThd1nGw14knkzl1Vr61RfMscx38R+GInRnVCqVTi6NGjscmUscE7w+hOnJRlXGZ8fBxVDU2W6XSyS2Uz71rlhlGPKCZZ2cQuf4k8co8blTTIMCJ3P/RyvzbGsAuvMUmpIz/HaZqtE9fGhpJwLp3MlnGZygSmMCJ3Pya7+JE9ULnwxo5MoJy68KLOunGJJNWRX5OsWqkTlyZ2JeVcmizTImFG7n7p5Z0O3nXToGy7JKmO/Gp3N9y9q+k6cWlsKCnn0iL3Fsnn8/T09NDX1xf4d7ky2cWlC89VklRHfrS7LdvHODJRqPlerTpxpa1Dcs6lOfcWyefzoQ2mujLZxaULz1WSVEd+tLu55JRadeJKW4fknEuX15ZxklwuF1oapCuz7Vy68FwlSXXkR7ubK8qtVSeutPWKfUk4l5Yt0yL5fJ5ly5aF9n0uTHaxGZWNSVodddru6qXgnjEvW/f/utDWK3ZA/M+lOfcWmJ6eZnx8PDZLD/iJKxeey1gdnaJeCu4XPnhhhFY1TxLOpWXLtICt424YzZGU6DfOWOTeAubcDaN5khD9xhnLlmkB26TDMIy4YLJMC1jkPjdJmLJtnMLOZ7wxWaYFcrkcfX199PT0RG1KKLRycbu2NojRGXY+44/JMi0Q5gSmqGl1fQ2X1gYxOsfOZ/yxSUwtUNlerxto9eJOypRto4ydz/gTeeQuIreKyCERebyq7EYReUpEdojInSKyyCtfJSITIvKo9/iHQKyuQ5izU6Om1Ys7KVO2/cC1PWvbwc5n/IncuQNfAy6bVXY/sEZVLwJ+AVxf9d4eVb3Ee3zCHzMbUygUmJiY6BpZptWLOylTtjvFr+Vio75B2PmMP5HLMqr6IPDKrLL7VLXovXwYeG0AtrVEt2XKtHpxu7Q2SJT4oVW7sJ64nc/4E4dsmd8BvlP1ekREtgN54I9V9Se1PiQiG4ANAMPDwx0bMVeOexJTxtqZYWiTVvzRql1ZT9zOZ7xR1cAcO3To3EXk80AR+KZXdAAYVtWXReRNwBYRuVBV87M/q6qbgc0Ao6Oj2okdUD9yT3LKmF3crePHnrU2mGn4QalUCtS5ty32iMjHgA8Av6Fe/0JVJ1X1Ze/5NmAP8Dof7GxIvR2YLGXMqMYPrbrTwcyo9XrDDVQ1ML0d2nTuInIZ8IfAlap6vKp8qYikvefnAKuBZ/0wtBH5fJ758+eTyczsjFiUZVTjh1bdyQ3CBb3ecIPIZRkRuQ14F7BERPYDX6CcHdML3O8Z97CXGfNO4E9FpACUgE+o6is1/7HP1Mtx96MbbiSLTuWsTlZUdEWvN6InaFmmoXNX1WtrFN9S59jbgds7NaodcrkcZ5555mnl9dattpSx+OLCAHm7NwjrSRoVnJRlXKRe5G4pY8ki7rKGTT4yKkQuy8SByclJJicn6+a4W1ZJcoi7rGE9SaNC5LJMHLB13LuHuMsatgNS9Lgg60HwskwinHu3zU7tZpIwQG49yehwad5L0LJMIjR3i9y7B1tTxeiEMOe9NJrPYJp7E+TzeUSEwcHBqE0xAsZkDaMTwpL1mukhmHNvgnw+z8DAQKD6leEOQcoaruixRjCEJes1M/BfKpUsFbIRuVzOJBmjY+KeZmk0JixZr5kegkXuTZDP51m2bFnUZsQWi1bLxDXN0s5f84Ql6zXTQzDn3gBVJZfLsXr16qhNiSUuZQ9ETRzTLO38tU4Y2UrNzGcIWpaJvXOfmJigWCzOkGUskmmeuEarzdJKW2gUbbnYrpJ+/uJKMz0Ei9wbMDvH3SKZ1ohjtNosrbaFuaItV9tVks9f3GnUQ7A89wbMznG39dtbI8lrnbTaFuZah8jVdpXk85d0TJZpwOzI3SKZ1mgUrbomQ7RCO22hXrTlaruytWrii0XuDcjlcqRSKQYGBgCLZFqlXrQKxD4t0M+24Gq7slVP44sTmruI3Ep5S71DqrrGK1tMeWPsVcBe4COq+qqUrf0b4ArgOPAxVX3Ef9PLVJb6rVSSRTKtUytaXbfpgdgP1PnZFlxuV7ZWTTxxRZb5GvB3wDeqyjYCP1TVTSKy0Xv9R8DllLfXWw28BbjZ+xsIs9dxt+np/uCqDNEKfraFuLarIKW1uMt2UeNE5K6qD4rIqlnFV1Hefg/g68CPKTv3q4BveJtmPywii0Rkhaoe8MPg2eRyOVauXDmjzCKZzknC6ovgb1uIW7sKMsPH1eyhOOGy5r6symG/BFSmiA4B+6qO2++V+c6dj+znlSM5vvXIYdtF3mds9cX4E2SGj6vZQ3HCFVlmTlRVRURb+YyIbAA2AAwPD7f8nVu2j/Hnd27jyowyoRmLHHwmrjKEcYogpbUoZLukyUBOyDJ1OFiRW0RkBXDIKx8DqnWS13plM1DVzcBmgNHR0ZZuDFB2OmdMvwoZ6JFyBBG3AT/XiZsMYcwkSGktbNkuiTKQy7LM3cB13vPrgLuqyn9LyrwVyAWht794ZIKXdR4Ak5qeUW4YRrDSWtiyXRJlICdkGRG5jfLg6RIR2Q98AdgEfFdEPg48D3zEO/xeymmQz1BOhfxtn20GyhHCgSMlALJSmlFuGEaw0lrYsl0Ssrdm44Qso6rX1nnrPTWOVeCTnRjVDJW84xOaoV8KgA34GcmkE605SGktTNkuKdlb1bgsy0RKZWZeIdXDfCnYzDwjkdgGImWSmL3lhCzjKlevHWJ81wpOnDjBLf/x0qjNMQzfsSV9yyQxe8sJWcZlBgYGOHz4cNRmGEYguKo1R5GWmLTsLZNlGjA4OMj4+Dhlqd8wkoWLC5aZVOQPtkF2AwYGBiiVShw/fjxqUxLHlu1jrNv0ACMb77EZwBHRjtYc9HlLYlpiFJgs04DBwUEAjh49yvz58yO2JjkkcdJIHGlVaw7jvLkqFcUNc+4NqDj38fHxiC1JFjaQ5w6taM1hnLckpiW2SydjD6VSyTT3uahs0nH06NGILUkWFp3FkzDOWxLTEtuh07EHVTXNfS6qZRnDP1wcyDMaE8Z5s92fynQ69mCyTAMymQx9fX0my/iMyzsPGfUJ67wlLS2xHTrtJQUty8TeuUM5encpck/C0qRJnDTSDdh5C49Oxx6ClmUS49xdidyTlGVi0Vk8sfMWDp32kmwSUxMMDAw4E7lbDrBhdAedjj2YLNMEFVkm6DthM1iWiWF0D530kkyWaYLKLNWJiQnmzZsXqS2u5AAnQfc3jCRjskwTuJQO6UIOsK39YRju4+wkJhE5X0QerXrkReQzInKDiIxVlV/hp8G1cGmWqgs5wKb7G4b7OCvLqOpu4BIAEUlT3gT7Tsrb6n1FVf/aFwubwKXIHaLPVuhm3T9uclTc7DX8obKKbRwGVN8D7FHV56MY0LQlCGbiiu4fNnFLQ42bvYZ/hOHc/eoTfBS4rer1p0Rkh4jcKiJn1PqAiGwQka0isrXTzTay2Sy9vb3m3D1c0P2jIG5yVNzsNfyj4tydXltGRHqAK4HveUU3A+dSlmwOADfV+pyqblbVUVUdXbp0aadmODWRKWpc0P2jIG5yVNzsNfyjVCoB7ssylwOPqOpBgMpfABH5KvB9H76jIa4tQRA1Uev+URA3OSpu9hr+ERdZ5lqqJBkRWVH13oeAx334joZY5G7ETY6Km72Gfzgvy4jIfOB9wB1VxX8lIjtFZAfwbuD3OvmOZqksQWB7qXYvcZOjrl47xIffNETai97SInz4Td3X4+pGnJdlVPUYcOasst/syKI2GRwcZHp6mhMnTtDfb93abiVOctSW7WPcvm2MaS8gmVbl9m1jjJ69ODa/wWiPuMgyTmDpkEbcsGyZ7sV5WcYlXJvIZBiNsGyZ7iUMWSZxzt0GVY24YFsZdi8my7SAyTJus2X7GOs2PcDIxntYt+kBW8QMy5bpZuK0/EDk9PT02CxVR7Fp9rWxLfG6l4os4+TCYS4yMDBgsoyDzDVw2O2OLE7ZPYZ/mCzTIjZL1U1s4NAwZmLOvUVslqqb2MChYcwkDFkmUc7dZqm6iQ0cGsZMbEC1RQYHBykWi0xOTtLX1xe1OYaHDRwaxkzMubdIdTqkOXe3sIHD6LFdn9zBZJkWsVmqhlEb2zTdLWxAtUVslqph1MbWsXELc+4tYrNUDaM2lo7qFjaJqUV6e3vp6ekx524Ys2h31yfT6YPBBlTbwGapGsbpfHb9+TOWgIDG6ai2bIR/zL5J/ufRBYDjsoyI7PV2XnpURLZ6ZYtF5H4Redr7e0bnpjaHzVI1jNNpZ5cq0+n9odZg9lcf3APEQ5Z5t6r+sur1RuCHqrpJRDZ6r//Ip++ak8HBQcbGLAPAMGbTajqq6fT+UOsmOVUsQdrxyL0OVwFf955/Hbg6oO85jYosY7NUDaMzbNkIf6h1MxTikS2jwH0isk1ENnhly1T1gPf8JWDZ7A+JyAYR2SoiWw8fPuyDGWUGBwcpFApMTU359j+bxdYsN5JEGMtGdMM1U+tmWHHprssyb1fVMRE5C7hfRJ6qflNVVUROC6NVdTOwGWB0dNS3MLt6IlNvb69f/7YhNvhkJI1ml41oN6OmW66ZWoPZvZmye3c6W0ZVx7y/h0TkTuDNwEERWaGqB0RkBXCo0+9plupc9yVLloT1tbZmuZFIGun0nTjobrlmat0kr7v4DPb+7BfuOncRmQ+kVPWo9/zXgD8F7gauAzZ5f+/q1NBmiWoJAht8MrqRThy0X9dMHHLxZ98kn3zySfb+zG1ZZhlwp3f3yQDfUtV/FpGfA98VkY8DzwMf6fB7miaqJQjanSRiGHGmEwfd7DUzl/OOq7Tj/PIDqvqsql7sPS5U1S965S+r6ntUdbWqvldVX/HH3Mb09PSQzWZ9idxbGeyxNcuNbqSTjJpmrplGC57FNRffeefuIiLiy45Mra6i184kEcOIO50ENc1cM42cdxzl0C3bx/iTLeXexW/8488CyxBK3PIDcGpHpk5oR0u0NcuNbqPTjVgaXTONnHfc5NBK0LiiNAU9cPDoZGAyUiKd++DgIAcOHGh84BzEMSIwjCgIMqhp5LzbWTMnSipB42D6BAA9FMkHlCGUOFkG/Fk8zGbnGUb0NJJ94iaHVoLDwVR5kqXOKveTxEbuU1NTTE5Otj2RKW4RgWEkkWZknzjJoZWeyIRmmVbhZZ1/stxvEuvcoZwO2a5zt02dDcMN4uS8G1EJGuczxXHNAhJY0JhI5149S/XMM89s+/8kqVEZhhE9FX/yo//7JMeKPQwFGDQm0rnbRtmGYbjK1WuHeP7BFCtXns3N11wa2Pck2rnbjkxGNxKH6fjdjKqSz+dP+qmgSKRz7+3tJZPJWORudB1xnY7fTRw7doxSqcTChQsD/Z5EpkL6NUvVMOJGXKfjdxO5XA6ABQsWBPo9iYzcwZ9ZqkZjOpUATELwF5t85z75fB7AIvd2sY2yg6fV9Xf8/rxxOjb5zn0qzj3oyD2xzt0i9+CpJwHccPeuplbTNAnBf2x1UvfJ5XKk02nmzZsX6Pck1rlXZqlGsZdqt1Cvq39kotBUNG4SQjD0Zk5d1mfMyzo9Hb8byefzLFiwINDlfiHhzh0sHTJImu3q14vGTULwl4rMdWSicLLsRKEUoUVGLfL5fOB6O3Tg3EVkpYj8SESeEJFdIvJpr/wGERkTkUe9xxX+mds8NpEpeGpJAPWoFY2bhOAvJnPFg1wuF7jeDp1lyxSBP1DVR0RkENgmIvd7731FVf+6c/Pap3oJAuN0/MhSqbX+zvGpIq8eL5x2bK1o3Nbv8ReTudynVCpx9OhRt527qh4ADnjPj4rIk4AzV6VF7vXxc6LL7PV3Zv9vmDsat/V7/CNuG1d0I+Pj46iq27JMNSKyClgL/NQr+pSI7BCRW0XkjDqf2SAiW0Vk6+HDh/0wYwZ9fX2k02nT3GsQZPc9Lutrt7I/blwwmct9wkqDBB8mMYnIAHA78BlVzYvIzcCfUV6H/s+Am4Dfmf05Vd0MbAYYHR3V2e/7YJflutch6O6769F4Uqfom8zlPpXZqWFE7h05dxHJUnbs31TVOwBU9WDV+18Fvt+RheCAdBcAAAsDSURBVB1gSxDUptu77+3sjxsXXL+xdjthRu6dZMsIcAvwpKp+uap8RdVhHwIeb9+8zrCJTLXp9u67DTwaUZHP58lms/T19QX+XZ1E7uuA3wR2isijXtnngGtF5BLKssxe4Hc7srADBgcHefbZZ6P6emfp9u57t/dckozraxWFNYEJOsuW+VegloX3tm+OvwwMDDA5OUmhUCCbzUZtjlN0c/fd9sdNJnEYS8nlcqHo7ZDgVSFhZjrk4sWLI7bGcIVu77kkFdfGUmr1IvL5POeee24o398Vzn18fNycuzGDbu65JBWXxlJq9SI+d8dj/HomnAlMkHDnbrNUjbBxXfNNMi6NpdTqRUjxBGTCSYOEBC8cBjZL1QgXW58+WlzKAqvVW5gv5RVqw4rcE+3c+/v7bZaqERq2cFe0uDQ7ulZvYb6U11wyWcYHRMRy3Y3Q8EvzNWmnfVwZS6mVkbUoXXbuJsv4hM1SNcLCj/XpTdpJBrV6Ee89b5De3l56e3tDsSHxzt0idyMs/NB8TdpJDlevHeKhjZfy3Kb389DGS1nSWwpNkoGEyzJQjtz37t0btRmJxSSEU/iRP+9SOp/hL2FOYIIucO4DAwOcOHHCZqkGQBxmBIZNp5rvXOl8cbuRxs3eWlT/hoX9WUTgyPFCW78nn8+zfPnyAK2dSeJlGdtLNThMQvCfetLOu39laay0+CSMHcz+DUcmCrx6vNDW7ykWixw7dizUyD3xzn3noUkA1t94X2I2ZXAFkxD8p14634+eOhyrG2kSbvy1fkM1rfyeyrifae4+sWX7GP/zX1/k8gz0M8XzPskGSehu+oFLMwKTRC1p5/e+82jNY129kSbhxt+Mrc3+njA36aiQaOd+4w92c6QgkIF/l93P+fpLCqT4p+8/R/bFYXp6elp6pNPprtGZm7mB2eqK7dFOcBC3G2nc7K1Fvd8w+5hmCHOTjgqJdu4vHpkgRZoJzVAgTVammccU2eJxdu06SqFQoFgsNv3/UqkUk6UUH0ilyPRNk0J5pTSPIinu+/4zlJ57DdlstuYjk8nUfa/6kU6nGxsSMM3ewGx1xdZpNzgI6kYaVC80CTf+Wr+hmlZ+j0XuPlO58377xCUzyocW9fPQH14KQKlUYmpqquajUCicVrb5x78gwzRnynF6pYgi9Mo0mWKB/fv3UygUTj5KpVLLNqdSqZZvCO3cRFKp+sMtrSyd6sqMwLjQ7rK0QdxIg+yFJuHGP/s3dJItk8/n6e/vDzVjT1R935u6/I9FLgP+BkgD/6iqm+odOzo6qlu3bvXdhtmNF8p3207Wm1i36YGaXbWhRf08tPHSGWXT09MUi8UZDr+VR7OfbeccptPpujeFn+x5laKmKFJ+THvPp0nx+Q++oaWbSRg7zlTj+njIyMZ7qHW2BHhu0/tDtaWVtmy0z5btY9z//TvIFCfY2j/qa5sUkW2qOlrrvUAidxFJA38PvA/YD/xcRO5W1SeC+L56BBE9tNLdTKfTpNPpQKcbqyqlUqntG0itm8jCzDSl6UkylMhIiTQlslLuhfzzP7eWbVTL+fvdI8lkMohILMZDXNKikzDo6TqVNvm+1ATHtCfUNhlI5C4ivwrcoKrrvdfXA6jql2odH1TkHhSuR4edUrvHk+KLV13A5ReeFWhPpJUxkGqy2SzHCspUKUVWpjmuWU5oOXbpzaRZO7zIl7rplF+OT/LcL48xXTp13aVTwsiS+SwZCGfNkQrbXzjCZPF0Pdml+oo7lTpelhrniPZz1+SFgH+9o9Ajd2AI2Ff1ej/wlllGbQA2AAwPDwdkRjAkXWdu1OPp7w8uylTVliSp6setP3mGDCXOSo1Tqtred6qGA4uKigPf98oEU8VpejJpVi7uD92xA6xc3F/zRrNycXwyWlyn3PaUE5rhuJ7S28PoHUU2oKqqm4HNUI7co7LDqE1UNzAROZl62ir/7ZFMXQ355o+ZhlyLpPdCo+ardcY1wpDhgnLuY8DKqtev9coMIzCSkH4XNknvhUZNlG0yKOf+c2C1iIxQduofBf5DQN9lGEAy0u+MZBFlmwwyFfIK4L9TToW8VVW/WO/YuA2oGoZhuEAUA6qo6r3AvUH9f8MwDKM+iV8V0jAMoxsx524YhpFAzLkbhmEkEHPuhmEYCSSwbJmWjBA5DDzfxkeXAL/02Rw/MLtax1XbzK7WcNUucNe2Tuw6W1WX1nrDCefeLiKytV4aUJSYXa3jqm1mV2u4ahe4a1tQdpksYxiGkUDMuRuGYSSQuDv3zVEbUAezq3Vctc3sag1X7QJ3bQvErlhr7oZhGEZt4h65G4ZhGDUw524YhpFAYuvcReQyEdktIs+IyMYI7VgpIj8SkSdEZJeIfNorv0FExkTkUe9xRQS27RWRnd73b/XKFovI/SLytPf3jJBtOr+qTh4VkbyIfCaq+hKRW0XkkIg8XlVWs46kzN96bW6HiLwxZLtuFJGnvO++U0QWeeWrRGSiqu7+IWS76p47Ebneq6/dIrI+ZLu+U2XTXhF51CsPs77q+Yfg25iqxu5BeRnhPcA5QA/wGHBBRLasAN7oPR8EfgFcANwA/NeI62kvsGRW2V8BG73nG4G/jPg8vgScHVV9Ae8E3gg83qiOgCuAfwIEeCvw05Dt+jUg4z3/yyq7VlUfF0F91Tx33nXwGNALjHjXbDosu2a9fxPwJxHUVz3/EHgbi2vk/mbgGVV9VlWngG8DV0VhiKoeUNVHvOdHgScp7yHrKlcBX/eefx24OkJb3gPsUdV2Zif7gqo+CLwyq7heHV0FfEPLPAwsEpEVYdmlqvepamUH8Ycp73AWKnXqqx5XAd9W1UlVfQ54hvK1G6pdIiLAR4DbgvjuuZjDPwTexuLq3GttwB25QxWRVcBa4Kde0ae8rtWtYcsfHgrcJyLbpLwhOcAyVT3gPX8JWBaBXRU+yswLLur6qlCvjlxqd79DOcKrMCIi20Xk/4nIOyKwp9a5c6W+3gEcVNWnq8pCr69Z/iHwNhZX5+4cIjIA3A58RlXzwM3AucAlwAHK3cKwebuqvhG4HPikiLyz+k0t9wMjyYUVkR7gSuB7XpEL9XUaUdZRPUTk80AR+KZXdAAYVtW1wO8D3xKRBSGa5OS5q+JaZgYRoddXDf9wkqDaWFydu1MbcItIlvKJ+6aq3gGgqgdVdVpVS8BXCag7OheqOub9PQTc6dlwsNLN8/4eCtsuj8uBR1T1oGdj5PVVRb06irzdicjHgA8Av+E5BTzZ42Xv+TbK2vbrwrJpjnPnQn1lgGuA71TKwq6vWv6BENpYXJ37yQ24vQjwo8DdURji6Xm3AE+q6peryqt1sg8Bj8/+bMB2zReRwcpzyoNxj1Oup+u8w64D7grTripmRFNR19cs6tXR3cBveRkNbwVyVV3rwBGRy4A/BK5U1eNV5UtFJO09PwdYDTwbol31zt3dwEdFpFdERjy7fhaWXR7vBZ5S1f2VgjDrq55/IIw2FsaIcRAPyqPKv6B81/18hHa8nXKXagfwqPe4Avg/wE6v/G5gRch2nUM5U+ExYFeljoAzgR8CTwP/AiyOoM7mAy8DC6vKIqkvyjeYA0CBsr758Xp1RDmD4e+9NrcTGA3Zrmco67GVdvYP3rEf9s7xo8AjwAdDtqvuuQM+79XXbuDyMO3yyr8GfGLWsWHWVz3/EHgbs+UHDMMwEkhcZRnDMAxjDsy5G4ZhJBBz7oZhGAnEnLthGEYCMeduGIaRQMy5G4ZhJBBz7oZhGAnk/wMIVbFCgZYYQAAAAABJRU5ErkJggg==\n",
            "text/plain": [
              "<Figure size 432x288 with 1 Axes>"
            ]
          },
          "metadata": {
            "tags": [],
            "needs_background": "light"
          }
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "HQzBljSeYuGt",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 100,
      "outputs": []
    }
  ]
}