Kirkpatrick–Seidel algorithm

ulti-chull.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Ultimate Planar Convex Hull Algorithm\n",
    "\n",
    "This notebook implement the algorithm from \"The Ultimate Planar Convex Hull Algorithm\" by D. Kirkpatrick and R. Seidel in 1986. The running time is $O(n \\log h)$, where $n$ is a number of input points and $h$ is a number of output edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from random import randint\n",
    "from collections import namedtuple\n",
    "\n",
    "\n",
    "Point = namedtuple('Point', 'x y')\n",
    "\n",
    "\n",
    "def flipped(points):\n",
    "    return [Point(-point.x, -point.y) for point in points]\n",
    "\n",
    "\n",
    "def quickselect(ls, index, lo=0, hi=None, depth=0):\n",
    "    if hi is None:\n",
    "        hi = len(ls)-1\n",
    "    if lo == hi:\n",
    "        return ls[lo]\n",
    "    pivot = randint(lo, hi)\n",
    "    ls = list(ls)\n",
    "    ls[lo], ls[pivot] = ls[pivot], ls[lo]\n",
    "    cur = lo\n",
    "    for run in range(lo+1, hi+1):\n",
    "        if ls[run] < ls[lo]:\n",
    "            cur += 1\n",
    "            ls[cur], ls[run] = ls[run], ls[cur]\n",
    "    ls[cur], ls[lo] = ls[lo], ls[cur]\n",
    "    if index < cur:\n",
    "        return quickselect(ls, index, lo, cur-1, depth+1)\n",
    "    elif index > cur:\n",
    "        return quickselect(ls, index, cur+1, hi, depth+1)\n",
    "    else:\n",
    "        return ls[cur]\n",
    "\n",
    "\n",
    "def bridge(points, vertical_line):\n",
    "    candidates = set()\n",
    "    if len(points) == 2:\n",
    "        return tuple(sorted(points))\n",
    "    pairs = []\n",
    "    modify_s = set(points)\n",
    "    while len(modify_s) >= 2:\n",
    "        pairs += [tuple(sorted([modify_s.pop(), modify_s.pop()]))]\n",
    "    if len(modify_s) == 1:\n",
    "        candidates.add(modify_s.pop())\n",
    "    slopes = []\n",
    "    for pi, pj in pairs[:]:\n",
    "        if pi.x == pj.x:\n",
    "            pairs.remove((pi, pj))\n",
    "            candidates.add(pi if pi.y > pj.y else pj)\n",
    "        else:\n",
    "            slopes += [(pi.y-pj.y)/(pi.x-pj.x)]\n",
    "    median_index = len(slopes)//2 - (1 if len(slopes) % 2 == 0 else 0)\n",
    "    median_slope = quickselect(slopes, median_index)\n",
    "    small = {pairs[i] for i, slope in enumerate(slopes) if slope < median_slope}\n",
    "    equal = {pairs[i] for i, slope in enumerate(slopes) if slope == median_slope}\n",
    "    large = {pairs[i] for i, slope in enumerate(slopes) if slope > median_slope}\n",
    "    max_slope = max(point.y-median_slope*point.x for point in points)\n",
    "    max_set = [point for point in points if point.y-median_slope*point.x == max_slope]\n",
    "    left = min(max_set)\n",
    "    right = max(max_set)\n",
    "    if left.x <= vertical_line and right.x > vertical_line:\n",
    "        return (left, right)\n",
    "    if right.x <= vertical_line:\n",
    "        candidates |= {point for _, point in large | equal}\n",
    "        candidates |= {point for pair in small for point in pair}\n",
    "    if left.x > vertical_line:\n",
    "        candidates |= {point for point, _ in small | equal}\n",
    "        candidates |= {point for pair in large for point in pair}\n",
    "    return bridge(candidates, vertical_line)\n",
    "\n",
    "\n",
    "def connect(lower, upper, points):\n",
    "    if lower == upper:\n",
    "        return [lower]\n",
    "    max_left = quickselect(points, len(points)//2-1)\n",
    "    min_right = quickselect(points, len(points)//2)\n",
    "    left, right = bridge(points, (max_left.x + min_right.x)/2)\n",
    "    points_left = {left} | {point for point in points if point.x < left.x}\n",
    "    points_right = {right} | {point for point in points if point.x > right.x}\n",
    "    return connect(lower, left, points_left) + connect(right, upper, points_right)\n",
    "\n",
    "\n",
    "def upper_hull(points):\n",
    "    lower = min(points)\n",
    "    lower = max({point for point in points if point.x == lower.x})\n",
    "    upper = max(points)\n",
    "    points = {lower, upper} | {p for p in points if lower.x < p.x < upper.x}\n",
    "    return connect(lower, upper, points)\n",
    "\n",
    "\n",
    "def convex_hull(points):\n",
    "    upper = upper_hull(points)\n",
    "    lower = flipped(upper_hull(flipped(points)))\n",
    "    if upper[-1] == lower[0]:\n",
    "        del upper[-1]\n",
    "    if upper[0] == lower[-1]:\n",
    "        del lower[-1]\n",
    "    return upper + lower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Sample input with random points in shape of circle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{Point(x=-15.639299513471565, y=-1.5749373246988085),\n",
      " Point(x=-15.357158815042107, y=1.1793444747238588),\n",
      " Point(x=-14.308869466644731, y=-7.697786666665838),\n",
      " Point(x=-12.941392875626052, y=12.49297423252657),\n",
      " Point(x=-12.277300895775557, y=-3.3620204732156367),\n",
      " Point(x=-11.910370093644298, y=0.593380561557634),\n",
      " Point(x=-11.83075465473005, y=-2.1021372394305935),\n",
      " Point(x=-10.65043353920354, y=-4.879947076443102),\n",
      " Point(x=-10.41073881727716, y=7.27847305836141),\n",
      " Point(x=-7.026561501198, y=15.898593659856772),\n",
      " Point(x=-6.604589971965105, y=-14.940947803655376),\n",
      " Point(x=-5.797130305071022, y=-13.268729953376063),\n",
      " Point(x=-3.868362334247486, y=-2.618856426094311),\n",
      " Point(x=-3.3606242332088065, y=16.574677187292423),\n",
      " Point(x=-2.4593265752920175, y=-15.466363022545725),\n",
      " Point(x=-2.411465130079165, y=17.72041218465447),\n",
      " Point(x=-1.8050906881180317, y=-11.555534250983746),\n",
      " Point(x=-1.544738842674569, y=13.711032885925),\n",
      " Point(x=-0.20013445625638582, y=-10.059714243539574),\n",
      " Point(x=0.20580737578159614, y=0.48886332548161704),\n",
      " Point(x=0.934929466485034, y=-16.13699207051679),\n",
      " Point(x=0.9987607636737117, y=-9.25939321185008),\n",
      " Point(x=1.5163489075834562, y=-15.97112691618583),\n",
      " Point(x=1.6980113664811753, y=-7.954572128085893),\n",
      " Point(x=1.9091520166566127, y=-6.119356669409068),\n",
      " Point(x=1.9306462723091364, y=16.00378441994944),\n",
      " Point(x=1.99108679285591, y=19.496565200256256),\n",
      " Point(x=2.4937740217105784, y=7.073355732835974),\n",
      " Point(x=4.071723288856472, y=-11.744474368447149),\n",
      " Point(x=6.310606585593494, y=12.18126701053351),\n",
      " Point(x=7.919821659625459, y=-9.003294448520256),\n",
      " Point(x=7.961359641011569, y=9.25859489412963),\n",
      " Point(x=8.894547781717371, y=-2.658260778998226),\n",
      " Point(x=9.297996941775452, y=7.5195869274143625),\n",
      " Point(x=10.127504409734186, y=9.957378817328994),\n",
      " Point(x=11.922374368323418, y=11.827931517868564),\n",
      " Point(x=12.663390743044609, y=-10.494734714229539),\n",
      " Point(x=13.73640533414023, y=-11.11988971122086),\n",
      " Point(x=15.697453542731594, y=-6.929099835398391),\n",
      " Point(x=15.870235319862296, y=7.5123572594491925),\n",
      " Point(x=16.655734795268046, y=9.262240951601363),\n",
      " Point(x=17.81742791037925, y=-1.6227526236395171)}\n"
     ]
    }
   ],
   "source": [
    "from random import uniform\n",
    "from pprint import pprint\n",
    "\n",
    "sample = 50\n",
    "radius = 20\n",
    "points = {Point(uniform(-radius, radius), uniform(-radius, radius)) for _ in range(sample)}\n",
    "points = {p for p in points if p.x**2 + p.y**2 <= radius**2}\n",
    "pprint(points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Output of the convex hull algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[Point(x=-15.639299513471565, y=-1.5749373246988085),\n",
      " Point(x=-15.357158815042107, y=1.1793444747238588),\n",
      " Point(x=-12.941392875626052, y=12.49297423252657),\n",
      " Point(x=-7.026561501198, y=15.898593659856772),\n",
      " Point(x=1.99108679285591, y=19.496565200256256),\n",
      " Point(x=16.655734795268046, y=9.262240951601363),\n",
      " Point(x=17.81742791037925, y=-1.6227526236395171),\n",
      " Point(x=15.697453542731594, y=-6.929099835398391),\n",
      " Point(x=13.73640533414023, y=-11.11988971122086),\n",
      " Point(x=1.5163489075834562, y=-15.97112691618583),\n",
      " Point(x=0.934929466485034, y=-16.13699207051679),\n",
      " Point(x=-6.604589971965105, y=-14.940947803655376),\n",
      " Point(x=-14.308869466644731, y=-7.697786666665838)]\n"
     ]
    }
   ],
   "source": [
    "answer = convex_hull(points)\n",
    "pprint(answer)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The output in a picture."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvAOZPmwAAIABJREFUeJzt3Xl8lNd56PHfmdE2WkcroA1J7IvEJuQFGyMvYEMcYzvO0sZxlsZOm/Q2vSn32kmbpE1c07hpe5u0SWiSxk2apDax8YJssM1iG2ODWIzYwUiAFrQgjfZllnP/mJEsQELrzDsz7/P9fPSRNJLmPDOSnved5z3nPEprjRBCiPBnMToAIYQQgSEJXwghTEISvhBCmIQkfCGEMAlJ+EIIYRKS8IUQwiQk4QshhElIwhdCCJOQhC+EECYRYXQAg6Wlpem8vDyjwxBCiJBy4MCBJq11+kjfF1QJPy8vj/LycqPDEEKIkKKUOj+a75OSjhBCmIQkfCGEMIkJJ3ylVI5SaqdS6oRS6phS6i98t6copV5XSp3xvU+eeLhCCCHGazLO8F3AN7TW84Abga8qpeYDjwNvaq1nAW/6PhdCCGGQCSd8rXWd1vqg7+N24ASQBdwHPOP7tmeA9RMdSwghxPhN6iwdpVQesAR4H5iita4D70FBKZUxmWMJESy2HKrh6W2nqHV0k2m3sWHNHNYvyTI6LCGuMWkJXykVD/wB+LrWuk0pNdqfexR4FCA3N3eywhEiILYcquGJ5yvodroBqHF088TzFQCS9EXQmZRZOkqpSLzJ/r+11s/7bq5XSk3zfX0a0DDUz2qtN2mti7XWxenpI64bECKoPL3tFHFtl3mw7iKrGy6Ahm6nm6e3nTI6NCGuMeEzfOU9lf8FcEJr/U+DvvQS8Aiw0ff+xYmOJYTRtNY4L16ka385XeXlfG/bW0ztaua9kr+hO2oKme0eDkW7ONHSbXSoQlxjMko6K4CHgQql1GHfbd/Em+ifVUp9CbgAPDQJYwkRUFpr+j78kK7y8oEk76qvB8Bqt1OXNp2XEldwLLadGJudJX2RrO6OYlUPvPPcGQpXZZGUHmvwoxDCa8IJX2v9DjBcwf6Oid6/EIGk3W56T526IsG7W1oAiEhPJ3b5cmKXFxNbXEzUjBkc/6CObQM1fA8VUb3kqwgeTk2hYmc1H+y4yPSFqRStyiZnXgrKMrprW0L4Q1DtpSNEoGmnk57jx+nav9+b4A8exNPeDkBkVhbxt902kOAjc3O5ejJC/4XZgVk6yTb+wjdLp9PRy9G3ajj2dg0v/+gD7FNiKVyVxdwbpxFlk389EXhKa210DAOKi4u1bJ4m/MnT20vPkSN07t9Pd3k5XYcOo7u99fao/PyPzuCXLSMyM3NSxnQ7PZw92EDFrmrqK9uIjLYy96ZpFK7KInlq3KSMIcxNKXVAa1084vdJwhfhzNPZSdfhw94z+PJyej44gnY6QSmiZ8/2JvjiYmKLlxGRlub3eOqr2qjYWc2ZA/V4XJqc+SkUrcomd2EqFin3iHGShC9Myd3aStfBgwM1+J5jx8DtBquVmPnzvcl9+XJily7BarcbFmdXWx/H36nh6O4aOlv7SEyLoXBVNnNvmkZMXKRhcYnQJAlfhI3rrWR1Xb5MV/kBX4LfT++pU6A1KjKSmKKigQRvW7wYa3zwlU/cbg/nDjVSsauaurOtRERZmH3DVIpWZZOaFW90eCJESMIXYeHqlaxp3Q6WOqr4QryDjMrj9J07B4CKicG2ZLGvPLMc26IiLDExRoY+Zo0X26nYWc3p/fW4nR6yZtspLM0mvygNi1V2MhfDk4QvQp7Wmvu/9SzplcdZePkchU3nmNbVDEBXZAzpN5f4EnwxtgULUFFRBkc8OXo6nBzfU0vF7mo6mnuJT4lm4cos5t+SiS0+PB6jmFyS8EXIud4ip9aoWI6mFnA0tYCKtAKqkjL58B/uNThi//J4NFVHmjiys5qaUy1YIyzMKplC0aps0nMTjA5PBJHRJnyZDCwMM5pFTv/enMDbsTlcTMhAq4/KGll2m1FhB4zFoihYnE7B4nQu13ZQsauGU+/VcfLdOqbNSKKwNJuCJelYpdwjRkkSvggY7XTSc+zYRwn+6kVOK1cSW7L8ikVOyw/V8PzzFWhfDR/AFmllw5o5Rj0MQ6RmxrPqj+Zw0/oCTrxbR8XuGrb//BixSVEsXJnFgluziE2Uco+4PinpCL/x9PbS/cEHdJWXD73IqbjYm+BHWOQk+81fS3s0549dpmJnNReON2OxKmYuy6CwNJup+UlGhycCTGr4IuA8nZ10HTpMV/kwi5z658APWuQkyXziWi51UrG7hpN763D2uMmYnkBRaTYzl03BGinlHjOQhC/8bmCRk6/+PvQip2Jily4dcpHT1VMuwVuueeqBQkn649DX4+Lk3ktU7KrGUd+FLSGSBbd6yz3xydFGhyf8SBK+mHQDi5x82xQMucipuBjbkiWjWuS0YuMOahzX7hufZbex5/Hb/fEQTEFrTfWJFo7sqqaqogmLUhQsSaewNJtpM5Ku2QBOhD6ZpSNGNFI5xXnpkvfs3Zfgr17klPa1r05okVPtEMn+ercHo2AsSSmlyJmfQs78FFobuzm6u5oT79Zx9kADaTnxFK7KZvbyKUREWQ2NUwSenOGb1DXlFK3J63Pw7dxe5tafpau8HGd1NQCW+Hhsy5ZO+iKnUD/DD6WSlLPXzel9lziys5rm2k6i4yKYvyKThbdlkZga/lNcw52UdMR1rdi4g5q2ZtbWvURRXSMLLrWQ1tMKeDs52YqXEbd8ObbiYmLmzkVZJ/9sMJQS5lBC8YCltab2tIMju6qpPNwIQF5RGkWl2WTNSZZyT4iSko4YUo+rh7eq36I57pfETznJmvd6SXNEUJG6kIo070rWXT/+Asri/9kd1zQPCZKSyGiFYklKKUXWnGSy5iTT3tzD0bdqOP52LZUfNJGSGect95RMISpGUkM4kjN8E3B5XOyr28fWyq28eeFNOp2dKHcivY5Copvm0uaeAb5VrMF8dhpsQvEMfygup5sz+70NWhovtBNli2DezdOkH28ICegZvlLql8DHgAat9ULfbd8Fvgw0+r7tm1rrsskYT4xMa80HjR/wauWrvFb1Gs09zSREJrB6+mrWFqylti6Tb71wnDaPe6AjsRlXsE7EhjVzhixJhdpzGBFpZd7N05h701QunWujYufFK/rxFq7KJlf68YaFyXrd9ivgx8B/XXX7P2ut/3GSxhCjcLblLGWVZZRVllHTUUO0NZrbsm9jbf5absm+hWirbz72NLAoa8iWU4JBqJekrqaUYtqMJKbNSPL24327hmNv1/KKrx/vwtuymHeT9OMNZZNW0lFK5QGvXHWG3zGWhC8lnfGp7ajl1cpXKass43TLaazKyo3TbmRtwVpuz7md+ChppCHGx+3ycPbAVf14b5xKYWm29OMNIgGfpTNMwv880AaUA9/QWrcM8XOPAo8C5ObmLjt//vykxBPumnua2V61nVcrX+Vgw0EAFqUvYm3+WlbnrSbN5v/+rMJcrunHOy+ZwtIcpks/XsMFQ8KfAjQBGvgeME1r/cXr3Yec4V9fp7OTHRd2UFZZxt7avbi1m5n2mawrWMfdeXeTnZBtdIjCBLz9eGs5+lYNnY5eEtNiWHhbNvNuln68RjE84Y/2a4NJwr9Wn7uPd2re4dXKV9l1cRc97h4y4zK5J/8e1hasZXbybKNDFCbldnuoPNzEkZ0Xvf14I339eEulH2+gGT4PXyk1TWtd5/v0fuCov8YKN26PmwP1ByirLGP7+e2097WTHJ3M+pnrWVuwlkXpi7Ao2QVRGMtqtTBzWQYzl2V4+/HuqubU+5c4/k4tmbPsFJVmk79I+vEGk0k5w1dK/Q5YBaQB9cB3fJ8vxlvSqQIeG3QAGJKZz/C11hxvPk7ZuTJeq3yNhu4GYiNiuSP3DtYWrOWGaTcQaZGXy0MJxv1szKq/H+/R3TW0N/cQnxzNwtukH6+/ydYKIaKqtWpgGuX5tvNEWiK5JesW1has5bbs27BFyD4n1xPq2zOEqyH78S7PoKg0R/rx+oEk/CBW31nPa1WvUVZZxvHLx1EoSqaWsLZgLXfk3kFStHQsGq1wWe0azi7XdnB0Vw0n37+Eq9fN1IIkikqzKVgq/Xgni+E1fHGl1t5WXj//Oq9Wvsr+S/vRaBakLmBD8Qbuzr+bjNgMo0MMSaG4n43ZpGbGc9sfzeHG9QWc3HuJI7uq2f6LY8Ru9vbjnX9LJnFJ0qAlECTh+1G3q5vdF3eztXIr79S8g8vjIi8xjz9d9Kfck38PeUl5RocY8jLttiHP8DPtUgoLNtGxkSy6I4ei0mxvP95d1ex7uZLysipmLM2gqDSbKfmJsmOnH0nCn2ROj5P3at+jrLKMNy+8SbermwxbBn88949ZW7CWeSnz5A96EoXLfjZmoiyKvMI08grTcNR3UbGrmhN76zizv56M6QkUlmYzS/rx+oXU8CeBR3s43HDYO42yajstvS0kRiVy1/S7WFewjqUZS7FapLuQv8gsndDX1+Pi1Hvefrwtl7z9eOffksnClVnEJ4+9m5rZyEXbSTRUQrlvcSanW05TVlnGq5WvUtdZR4w1htKcUu7Jv4cVWSuIsso0NCHG4up+vEopChanU1SazbSZ0o93OJLwJ8nV0/5UZDO25CNMyzxBQ+95rMrKzZk3D2xUFhsp+4cLMRlaG7s5+lYNJ/bU0tvlIjU7nqJS6cc7FEn4k6R/2t8NSc9yOfkk9bYuAKy9M3hi5We4K+8uUmJSDI5SiKGFQ7nL2efm9Pvecs/lmkH9eFdmkZgmF+dBpmVOmv7pfQW2D+i0uOitX4uzbRG47Hzq0XUGRyfE8K5+dVrj6OaJ5ysAQirpR0ZZWXCrd/pm7RkHFTurOfzGRQ6/foG8ojQKS7PJln68oyIJfwSZdhuq9QLfc1TyT42f4qj7NsC7sEeIYPb0tlNXzF4C6Ha6eXrbqZBK+P1ePFw78GplZqaNz6alUHe2lcoPmkieFkfRqixm3zBV+vFeh8x7GsGGNXO4P/I9IoCXPDcBMu1PhIZwWpTW/2qlxtGNBs50dLOx5hIpn8rj9s/NIyLSwu7fneaZJ97lnWfP4GjoMjrkoCSHwhGsX5JF686DHGmfS43OICtE66DCfMJpUdpwr1b+8c0z7Hn8dubeNJX6yjaO7LhIxa5qPth5kekLUikslX68g0nCH0n9cZLaTlF0z9NU3iA1exE6wmlR2kivVpRSTC1IYmpBEp2tvRx7q4ajvn68SRk2Cm/LZu7N04g2eT9ecz/60Ti6GZQVFqw3OhIhxiScmqyP5dVKXFI0JfcWsOyePD482MCRndW889wZ3n/pHHNunErhqmxSppmzH69My7wereH/LYLUmfDw80ZHI4RpTXQb7IbzbRzZWc2Zcm8/3uy5yRSVZjO9MC0s+vHKtMzJUF0OjvOw6nGjIxHC1Cb6aiVjeiJ3fn4+Nz8wc6Afb9lPKrz9eFdmM2+FOfrxyhn+9ZT9HzjwK9hwFmISjY5GCDFJ+vvxVuyqpvaMI+T78coZ/kS5XXDsBZhztyR7IcLM4H68TdXtVOw0Rz/eSUn4SqlfAh8DGrTWC323pQD/A+Th7Wn7Sa11y2SMFxBVb0FnAyz8hNGRCCH8KC07gdKH53HTAzO9/Xh31fDapqPEJ0ezYGUWC27JxJYQHhshTlYT85VAB/BfgxL+D4BmrfVGpdTjQLLW+v9e736CqqSz5c/gxMvwV2cgUrZnFWKiQmVfn/5+vBW7qqk+6evHW5xBYWk2GdOD89V+QEs6Wuu3lFJ5V918H7DK9/EzwC7gugk/aDh7vMl+3scl2QsxCUJpXx+Lxbslc8HidJprO6nYVc3J9y9x8r1LTC1IpLA0mxlLMrBGhF65x58RT9Fa1wH43odO09Yz26G3DQofNDoSIcLC9fb1CWYpmXHc9kdz+PxTN3PLQ7Pobnfy+i+O81/ffJd9r1TS2dprdIhjYvhFW6XUo8CjALm5uQZH41PxHMRlQN5KoyMRIiyE+r4+1/bjrWH/K5UceDW0+vH6M+HXK6Wmaa3rlFLTgIahvklrvQnYBN4avh/jGZ2eNji9DYq/AFbDj4dCGGYya+7hsq/PNf14d1dz8l1vP9703ASKSrOZWZzBK0cvBeX1Cn+WdF4CHvF9/Ajwoh/HmjwnXwF3r8zOEaZ29e6U/TX3LYdqxnV/G9bMwRZ5ZZeqUN3Xp599Siy3fnI2j2xcwcpPz8bV5+bNZ07wHxve4cVfH6e1eXKeu8k0KQlfKfU7YC8wRylVrZT6ErARuEspdQa4y/d58Kt4DuzTIXvEC95ChK3JrrmvX5LFUw8UkmW3ofD2kxjttgjBLiomgsJV2XzmOzfw8b9YzAXlZlmXhT9pquJLNa8S49ZBc71ismbpfGaYL90xGfcfMB0NcG433PKXEOS1OCH8yR819/VLssIiwQ9HKUXOvBR+H91NYoTijpZOsvqqiPB0gTUuKK5XhN68In86tgW0GwqlnCPMbbjaeqjV3I2QabfRatW8H2cHIMV5eeB2o0nCH6ziOZiyEDLmGR2JEIYKx5p7oPQ/d5ejUgFIdTYHzXMn01D6tVRB9T6487sGByKE8cJpL/1AG/zcddbEkkMrjwTJ9QpJ+P2O/sH7fqEsthICwr/m7k/9z93mJ3fS3d4WNM+jlHT6VWyGnBvBHiSLv4QQIS8tN4/m6ot4PO6RvzkAJOED1B+DhuNysVYIManScqbjcvbhuFRndCiAlHS8Kvr71t5vdCRChKxQ2Q1zsozm8abn5gHQdKGKlMxsA6K8kiR8rb2NymeUQlxawIc32z+JCE+htBvmZBjt403JzkEpC40XzjP7xlsMiXUwKelU7wfHBSh8KOBDT/bydREcthyqYcXGHeQ/vpUVG3eY4vcZqrthjtdoH29kVDT2qdO4fPF8IMMbliT8iucgIgbmrgv40Gb7JzEDsx7EQ303zLEay+NNy51O08UqP0c0OuZO+P19a2ffDdEJAR/ebP8kZmDWg7jZVuaO5fGm5Uyn5VIdzt4ef4c1InMn/Mrd0NloSDkHzPdPYgZmPYibbWXuWB5vWm4eaM3l6osBim545k74FZshOglm3WXI8Gb7JzEDsx7Ew3k3zKGM5fGm5eQB3pk6RjPvLB1nt7dv7YL7ICLakBBk+Xr42bBmzhWzN8A8B3Gzrcwd7eO1T51KRFR0UNTxzZvwz2yHvnbDyjn9zPZPEu7kIC6uZrFYSc3OoeniBaNDMXHCr3gO4qdA3q1GRyLCjBzExdXScvKo+uCA0WGYtIbf0wqnt8OCB8BiHfn7hRBiAtJycul0tNDV1mpoHOZM+Cd8fWsNLucIIcwhbWCLBWMXYJkz4Vc8B8n5kLXU6EiEECYwkPANvnDr9xq+UqoKaAfcgEtrbWx38PZ67/z7W78hfWuFEAERZ08mJiHR8KmZgbpoW6q1bgrQWNd3fAtoj5RzhBABo5QiPWc6TQbvqWO+kk7FczClENLDf160ECJ4pOZMp+niBbTHY1gMgUj4GtiulDqglHo0AOMNr7nSuzumNDoRQgRYem4ezp5u2poaDIshEAl/hdZ6KXAP8FWl1MrBX1RKPaqUKldKlTc2Nvo3EulbK4QwSFrudAAaDZyp4/eEr7Wu9b1vAF4ASq76+iatdbHWujg9Pd2fgXjLObk3gT3Hf+MIIcQQ0nK8Cd/IC7d+TfhKqTilVEL/x8Bq4Kg/xxxW/TFoPCnlHCGEIaJssSSmTzH0wq2/Z+lMAV5Q3umPEcBvtdav+XnMoR3dDJYImC99a4UQxkjLyTX0DN+vCV9rfQ5Y5M8xRsXjgYo/QEEpxKUaHY0QwqTScvOo+uAgbpcTa0RkwMc3x7TM6n3QakzfWiGE6JeWm4fH7aa5ptqQ8c2R8Cs2Q4QN5q41OhIhhImlG3zhNvwTvtvp7Vs7x5i+tUII0S85MxuLNYJGgy7chn/CP7cbupqknCOEMJw1IoKUrGwuS8L3k6ObISYJZt5pdCRCCEFaznQapaTjB/19a+d93LC+tUIIMVhaznTamxrp7eoM+NjhnfBPvwZ9HVLOEUIEDSOboYR3wq/YDPFTIe8WoyMRQgjAu4kaGNMMJXwTfrcDzmyHhdK3VggRPBLS0omy2QzZRC18E/6Jl8HdJ3vnCCGCilKK1JzphszUCd+Ef3QzpBRApvStFUIEl/ScPJouVKG1Dui44Znw2y9B5Vuw8BPSt1YIEXTScqfT09lBR8vlgI4bngn/2Au+vrVSzhFCBB+jZuqEVcLfcqiGFRt3cKjs55xSBWypjjc6JCGEuIZRzVDCJuFvOVTDE89XYG2tYonlLH/ou4Ennq9gy6Eao0MTQogr2BISiUtOkYQ/Xk9vO0W3083HLe8C8LL7Zrqdbp7edsrgyIQQ4lppOdNpunghoGP6u+NVwNQ6ugE4q7P4T9ca6ki94vZA2HKohqe3naLW0U2m3caGNXNYvyQrYOMLIUJHWm4eh7e9gsftxmINzFqhsEn4mXYbNY5uXvOU8Jqn5IrbA6G/pNTtdANQ4+jmiecrACTpBzk5UAsjpOfm4XY6ablUS2pWTkDGDJuSzoY1c4iJuPLh2CKtbFgzJyDj95eUBpOSUvDrP1DXOLrRfHSglms/wt8+unAbuJk6fk/4Sqm7lVKnlFJnlVKP+2uc9Uuy+NrtMwc+z7LbeOqBwoCdqQ1XOgpkSUmMnRyohVFSsnNQyhLQPXX8WtJRSlmBfwPuAqqB/Uqpl7TWx/0xXnZyLADb/3Ils6cEtrtVf0lpqNtF8JIDtTBKZFQ09qnTAjpTx99n+CXAWa31Oa11H/B74D5/DXa6vp0IiyIvNc5fQwxrw5o52CKvvPASyJKSGJ/hDshyoBaBkJY7naYA7qnj74SfBVwc9Hm177YBSqlHlVLlSqnyxsbGCQ12ur6D/LQ4oiICf2li/ZIsnnqgkCy7DUXgS0pifORALYyUlpOHo/4Szp6egIzn71k6Q21kc8VuQVrrTcAmgOLi4gntJHSmoZ2FmUkTuYsJWb8kSxJ8iOn/fcksHWGE9Nw80JrL1ReYOnO238fzd8KvBgbPN8oGav0xUHefmwvNXdwv/6hijORALYySluudqdN4sSogCd/ftY/9wCylVL5SKgr4NPCSPwb6sLEDrQn4xVohhBivpClTiYiKDtjUTL+e4WutXUqprwHbACvwS631MX+Mdbq+HYDZU2TDNCFEaLBYrKRm5wRspo7fV9pqrcuAMn+Pc7q+g0irYroBM3SEEGK80nLyqDxcHpCxwmKl7ZZDNfxqTyVOt2bV07tklaQQImRcstrpanUwb8NmVmzc4df8FfIJv39pfI/LA8jSeCFE6NhyqIbfnOoDILXvst/zV8gn/Ke3naJHXyZm2v9gifY+SbI0XggRCp7edopai53cuHnMcnYC/s1fIb9bZq2jG22JIiLxCNodR29D1sDtgSa7LgohxqLW0U2+NZ6S9HVE91Szc9Dt/hDyZ/iZdht4YnF1ziEi8QPA89HtASS7Lgohxio7ycYTKpZ24G+jP5pS7q/8FfIJv39pvKt1CZbIdqyxHxqyNF52XRRCjNUP8qYwDyv/pHq5bPEWXPyZv0K+pNNfMvnBNkWbezNJ6RV8+8aHAl5KkV0XR0fKXuFFfp/j52zsIudYCy1ZsZzqcKJaXX5/DkM+4cNHS+O/vWcP289v5+7C1IDHINsjj0y6goUX+X2On/ZoWjafQUVYmf9IIXsSowIybsiXdAZbV7COTmcnu6p3BXxs2XVxZFL2Ci/y+xy/zr219J1vw35vAdYAJXsIs4RfPKWYDFsGW89tDfjYsj3yyKTsFV7k9zk+ruYeWl+rInp2MrFLMwI6dliUdPpZLVbWFqzlN8d/g6PHgT3G7tfxhqpf7nn8dr+OGcqk7BVe5Pc5dlprWp4/AxZF8gMzUWqoHeT9J6zO8MFb1nFpF9vPb/frODINc+yk7BVe5Pc5dl376+k96yBpbT4R9piAjx92CX9O8hxmJM3we1lH6pdjJ2Wv8CK/z7Fxtfbi2HqO6IIk4pZPNSSGsCrpACilWFewjn899K/UdNSQFe+fPz6pX46PNBsJL/L7HB2tNY4XzoJHk/zgLJQlsKWcfmF3hg+wtmAtAGXn/LcrszS/FkKMVvfhRnpONpO4Jo+IVONyRFgm/Kz4LJZmLGXrua1oPaE2ucOS+qUQYjTc7X04Xv6QqNwE4m/ONDSWsEz44L14+2Hrh5xq8U9NXeqXQojRcLz0IZ5eN8mfmG1YKadf2NXw+62evpqn3n+Kree2Mjdlrl/GkPqlEOJ6uiqa6K5oInFNHpEZsUaH478zfKXUd5VSNUqpw763tf4aayj2GDu3ZN1C2bky3B73yD8QYFsO1bBi4w7yH9/q9y43QojAc3c6cbx4lsiseBJWBseJob9LOv+stV7se/N7X9urrZuxjobuBsrrA9MvcrRkDr8Q4a/1lXN4ulzeWTnW4KieB0cUfrIqexVxkXGGbLVwPTKHX4jw1n2yma5DDSSsyiYqM97ocAb4O+F/TSl1RCn1S6VUsp/HukZMRAx35N7B6+dfp9fdG+jhhyVz+IUIX54eF47nzxAxJZbE23ONDucKE0r4Sqk3lFJHh3i7D/gJMANYDNQBPxzmPh5VSpUrpcobGxsnEs6Q1hWso8PZwe6Luyf9vsdL5vALEb5ayypxt/eR8onZqIjgKqJMKBqt9Z1a64VDvL2ota7XWru11h7gP4CSYe5jk9a6WGtdnJ6ePpFwhnTD1BtIs6UFVVlH5vALEZ56zrbQue8S8bdmE5WTMPIPBJg/Z+lMG/Tp/cBRf411PVaLlXvy7+Htmrdp7W01IoRryBx+IcKPp9dNy/NniUizkXRXcJVy+vlzHv4PlFKLAQ1UAY/5cazrWlewjl8f/zWvn3+dT8z+hFFhXEHm8IcHafEn+rVtq8Ld3EP6Y0Woq17BBwu/JXyt9cP+uu+xmp8yn7zEPF4590rQJHwR+qTFn+jXW9VKx95a4m6aRnR+ktHhDCu4rij4Sf8OmgfqD1DXUWfO4M8GAAAUgElEQVR0OCJMyPRaAaCdblo2n8GaFE3S3flGh3Ndpkj44C3rAJRVBnz9lwhTMr1WALS9cQFXUzfJD87CEh2cpZx+pkn4OQk5LEpfxNbK4JmtI0KbTK8VfRfbaX+rmtjiKcTMCvhSozEzTcIH71n+mZYznGqWl9xi4mR6rXltOVTDyqd2sPffDtCMZk9O4NsVjoepEv6avDVYlVXO8sWkkOm15tR/sf721l5mYGWj7ub/vHI8JPbCCtvtkYeSEpPCiqwVvFr5Kl9f+nUsylTHO+EHMr3WfJ7edorZrg4io0+wxTmHdz1x4PTeHux/C6bLeOvy13Gp8xIH6g8YHYoQIgQ1OdqZHXkaNxE844keuD0ULtab6gwfYFXOKqIsMTz2wn/Qcr5BFssIIUbN4/FwZ+x5YtxOXuqbS9OgFBoKF+tNl/C3H22hxzEfFXcIrdbJYhkxLrLC1pz27NlDuqeZAzqPJv3RtsehcrHedCWdp7edos9RhLL2sCLhBRQeWSwjxkQa2JhTZWUlO3bsYOHChXxx/Z0hebHedGf4tY5uUkknvQ8ejNrOX0VV8HfOhznsmGV0aCJEXG+FbSj804uxa2trY/PmzaSmpnLvvfcSHR3N/UuzjQ5rzEx3hp9pt9FEKic/fJI9zQ+TqZp4Ifo7/Cz2p9BabXR4IgTICltzcbvdbN68mb6+Pj75yU8SHR098g8FKdMl/P7FMhorf/CspLT3n/ip537u4D34UTHs2gh9XUaHKYKYrLA1lzfffJMLFy5w7733kpGRYXQ4E2K6hH/1YplkezJT738S65/vh9lrYNdT8ONiOPIcaG10uCIIyQpb8zhx4gTvvvsuy5cvp6ioyOhwJkzpIEpqxcXFury83NggqvbAa4/DpSOQXQJ3b4TsZcbGJIKOGWbpmOExXs/ly5fZtGkTqampfPGLXyQiIngveSqlDmiti0f8Pkn4Q/C44fBv4c2/g84GKPo03PkdSMw0OjIhAuLqvf7B+yomVGajTJTT6eTnP/85ra2tPPbYYyQnB/fGaKNN+KYr6YyKxQpLH4Y/PwArvg7HnocfLYPdT4NTLsyZyZZDNazYuIP8x7eyYuMO00y9NPte/2VlZdTX1/PAAw8EfbIfC0n41xOTCHf9LXz1fZh5B+z8Pvy4BI4+L/V9EzDzfHszz0Q6ePAghw4d4tZbb2X27NlGhzOpJOGPRkoBfOo38MjLEJMEm78A/3kP1B4yOjLhR2Y+yzXrTKS6ujrKysrIz8+ntLTU6HAm3YQSvlLqIaXUMaWURylVfNXXnlBKnVVKnVJKrZlYmEEifyU8ths+9i/QdAY2lcKWr0L7JaMjE35g5rNcM85E6unp4dlnn8Vms/Hggw9isYTf+fBEH9FR4AHgrcE3KqXmA58GFgB3A/+ulAru3l+jZbFC8Rfgfx2Em78GR/7HW99/+4fg7DE6OjEKo63Lm/UsF8y317/Wmi1btuBwOHjooYeIj48f+YdC0ITmGWmtT4C3SfhV7gN+r7XuBSqVUmeBEmDvRMYLKjFJsPr7sOwLsP1vvDN6DjwDq78H8z4O1z4nIghcPfvkepvnbVgzZ8iZKuF8ljuYmfb637t3LydPnmT16tXk5uYaHY7f+Os1SxZwcdDn1b7bwk/qDPjMb+FzL0JUHDz7OfjVx6DuiNGRiSGMpS5vtrNcszp//jyvv/468+bN46abbjI6HL8a8QxfKfUGMHWIL31La/3icD82xG1DTmtRSj0KPAqE9pG1YBU89jYc/BXseBJ+ttI7tfP2v4H40F6OHU7GWpc301luKBvvIrGOjg6ee+45kpOTue+++4aqVoSVERO+1vrOcdxvNZAz6PNsoHaY+98EbALvwqtxjBU8rBGw/E9g4Sdg9w9g38/g6Auw8q/gxj+FiNDddClcZNpt1AyR3M1Qlw9XYynTDda/KVpPTw+f/exniYkJjUbkE+Gvks5LwKeVUtFKqXxgFrDPT2MFH5sd7v57+LP3YPrN8MZ34N9ugBOvyPx9g5lx9km4G+/02V27dlFVVcW6deuYOnWoIkb4mdBFW6XU/cCPgHRgq1LqsNZ6jdb6mFLqWeA44AK+qrV2X+++wlLaLPjjZ+HsG7DtW/A/f+yd2rnmKZi60OjoTKn/jM/Me8SEm7GU6fpLP5a2Ou6IOkPK9DksWbLE3yEGDdlLJ1DcLjjwn7DzSehphaWPwO1/DXFpRkcmREhbsXHHkGW6LLuNPY/fPvB5f+nH6uri3qhjdOhoduqFfP+BRSF/wJe9dIKNNQJKvgx/fhBKHoWD/wX/ugTe/RG4+oyOLuSYdY8bca3RlOk8Hhf//c5rrMzczuNLfkxGWhW7nDPocGpTrJzuF7z7fYar2BS45x+g+Iuw7Zuw/a+h/D9hzZMw+26Zvz8K471IFwrMviXxeAxZpludx235tVRWbcHh2E9r60G+sqATgPauJN4jmXbtvUhrhpXT/aSkY7Qzr3sTf9NpKCiFu5+CjHlGRxXURvsSPtSYfUviiXC5OmltO4TDsQ+HYz9tbYfxeLyvnOPj5mC3l/DD3Tber86htS+RwTPHQ/3vBkZf0pEzfKPNuss7h3//z73dtn6ywrt1w6pvQlyq0dEFpXDd40aao4+e0+nA0XpgIMG3tx9FazdKWUmIX0B21sPY7SXY7cVERtoBWNtVw9sXKwBzrpwGSfjBwRrpnadf+Elv0i//JVQ8B6ue8M7rt0YaHWFQCde59OF6IJsMvb2NA8nd4dhHR6e37q5UFEmJi5ie+xh2ewlJSUuIiBh6HxyZoSUJP7jEpcK6f4TlX4LXnvC2Wtz/C1jz9zB7tdHRBY1w3eMmXA9kY6W1pqenZiDBtzj20d1dBYDVGktS0jIKpqzDbi8hMaEIq3X0CxrNvnJaEn4wypgHD78Ap7d56/u/fQhm3ulN/OmhndQmQ7ieqYXrgWwkWmu6us5dkeB7e+sAiIhIwm5fTlbWZ0i2lxAfPw+LRV7xjpdctA12rj7Yt8m7VUNfh7fEs+px72wfEXbMMEtHazcdHadwOPbR4ivROJ3NAERFpWO3L8duLyHZXkJc3CyUktnjI5Em5uGms8m7aOvAr7xbM6/6pndqp1VepIng5vH00d5+bCDBt7aW43K1AxATk43dvpxkewl2+3Jstryw38DMHyThh6tLR2HbE1D5FqTP9c7fnzme/e2E8A+3u5vWtsMDF1hbWw/j8XivTcTGzrgiwcfEZBocbXiQaZnhaupC+NxLcKrMuz/Pbx6EWWu8iT9tlt+GNUOpQYyPy9XumyLpTfBtbRVo7QQUCfHzycr8lK9MU0xUlGwlYiQ5ww9lrl54/6ew+2lwdUPJY3DbBrAlT+owsiBIDNbX14yjdf9Agm9vPwF4UCqCxIRC3/z35SQlLSMyMtHocE1BSjpm0tEAO77v3Z/Hlgy3fwuWfn7S6vvhurJVjE5P7yUcLfsGknxn5xkALJZokhKXDErwi7FaYw2O1pykpGMm8Rnw8X/1zuB57QnY+o2P5u/PKJ3w3cuCIPPQWtPdfWHg7N3h2E93zwUArNZ47PZlTJ2yHnvychITCrFYogyOWIyFJPxwMq0IPv8KnHjZuynbr9fDnLXeZuupM8Z9t7IgKHxp7aGz84wvwXvfevvqAYiMTMZuX052zuew25eTED8Ppawj3KMIZpLww41SMP/jMGs1vPfv8PYPvd22bvwKrNzgndI5RmZdEBSOPB4XHR3HBxY4ORzluFwOAKKjp2JPLhko0cTFzpQpkmFGavjhrv0S7PgeHPpviE31Nl1Z+jmwjO1MTWbphCaPp5e2tgrfHPh9tLYexO32bhNss033LXDyLnSKicmWBB+i5KKtuFLtIW99/8JemFLo3YY5/1ajoxKTzO3uorX1kO/sfT9tbYcGtgmOi5s9KMEvJzp6isHRiskiCV9cS2s4vgW2fxtaL8Dcj3nr+yn5RkcmxsnpbKW19cBAgvduE+wCLCQkLBhY4OTdJnhyp+uK4BGQhK+Uegj4LjAPKNFal/tuzwNOAP29w97TWn9lpPuThB8gzm7Y+2N4+5/B44Qb/wxu/QZbTrRL2SbI9fY1XTGDpqPjJKBRKorExKKB8ox3m+AEo8MVARKoaZlHgQeAnw3xtQ+11osneP/CHyJt3gu4iz8Lb/4t7PkXesp/TXn3J6jruxWNJazaBoay7u7+bYK98+C7uioBsFhs2JOWUpD/F95tghMXYbXGGBytCHYTSvha6xOAXOgJVYnT4P6fQsmXOf3zP+P7lp/x6ahtfNf5Ocr1XLqdbp7ceoIVM9NIjYvCYpHfsz95twmuvKLRR09vLQAREYnY7cvJzPwUdnsJCfHzZZtgMWb+nJaZr5Q6BLQBf621ftuPY4mJyFrGfd1/w72WvfzfyN9RYjlFuXsuAI0dvSx/8g2sFkVqXBQZidFkJMSQkRBNekK0730MGYnRpMd7b4uJnLy52uE8O8i7TfDpK/aBdzovAxAVlYbdXkKu/cvY7SXEx82WbYLFhI2Y8JVSbwBTh/jSt7TWLw7zY3VArtb6slJqGbBFKbVAa902xP0/CjwKkJubO/rIxaTKtMfykuNmtvcuw8NHiSUlNoqv3zWLhrZeGtp7aGjvpb6th4qaVi539OIZ4hJQki3yigNCRuJHBwjvbd4DREJ0xHVfHV69h0+ol5k8HufANsEOx34creW4XN5/iZiYLFJTbx3YB162CRb+MGLC11qPee9drXUv0Ov7+IBS6kNgNnDNFVmt9SZgE3gv2o51LDE5Plpc9VG7OFuklW/fO3/Y5Opye2ju7KOhvZfGdt8Boa33is/Lz7fQ0N5Ln8tzzc/HRFo+OgAMvFrwfp6eGM2TW0+EdFNvt7uHtrYPBiX4g4O2CS4gI+Me7yKnpOXYbMH/eETo80tJRymVDjRrrd1KqQJgFnDOH2OJyTGetoERVov37D3x+hcLtda09bhoHHRAaGjv8R0Uemlo6+V0fTt7zjbR1uMaMdYaRzc/3H5q0KuGj15BTGY5aTjDlZlcrnZaWw8OdHHybhPcByji4+eSmfnQwCrWaNkmWBhgotMy7wd+BKQDDuCw1nqNUupB4O8AF+AGvqO1fnmk+5NpmaLH6R54dfDlZw7Q3NV3zff0XzseqpyUGBMxUELKuKqENPiaQ2LM9ctJMHRiBwbKTPGRHcyyn2N+2jluy6vB6j5D/zbBCQmFAwucvNsEj31LCyFGSxZeiZB3vX34712UyeWO3mvKSY0dvVdcbxiunBQdYRm4AJ0eH+372Pd5QjTHalv58Y6z9Lg8aEDbrEQmRaMSI/HE9ZGY2sPnLL9gEYfpc0dS01nA7UWrfQl+iWwTLAJKtkcWIW+kMtN4y0kDBwhfOelsYwfvfjh0OUkDRFnouyGdvmhvuUh1O5nmamBvQzFltauoas3BrSP5k/XrJvXxCzHZJOGLoLZ+SdaELtAqpUiyRZJki2RmxvVXng4uJz34k73eG2Ms6GgrEWdasXS4UR1OlFtTQwI1FA38bJZsFS1CgCR8IXxiIq3kpMSSkxJLlq8HgOrxoHo8WFqdACTHRtLj9MhW0SIkyUoOIYawYc0cbFfN+LFFWvnOvQt46oFCsuw2FN4ze+ntK0KFnOELMYSRrh9IghehSBK+EMOY6PUDIYKNlHSEEMIkJOELIYRJSMIXQgiTkIQvhBAmIQlfCCFMIqj20lFKNQLnJ/lu04CmSb7PQAjFuEMxZgjNuEMxZgjNuEMh5ula6/SRvimoEr4/KKXKR7OpULAJxbhDMWYIzbhDMWYIzbhDMebhSElHCCFMQhK+EEKYhBkS/iajAxinUIw7FGOG0Iw7FGOG0Iw7FGMeUtjX8IUQQniZ4QxfCCEEYZzwlVIPKaWOKaU8SqniQbfnKaW6lVKHfW8/NTLOqw0Xt+9rTyilziqlTiml1hgV4/Uopb6rlKoZ9PyuNTqm4Sil7vY9l2eVUo8bHc9oKaWqlFIVvuc3aHuCKqV+qZRqUEodHXRbilLqdaXUGd/7ZCNjvNowMYfM3/RIwjbhA0eBB4C3hvjah1rrxb63rwQ4rpEMGbdSaj7waWABcDfw70op67U/HhT+edDzW2Z0MEPxPXf/BtwDzAc+43uOQ0Wp7/kN5umCv8L7tzrY48CbWutZwJu+z4PJr7g2ZgiBv+nRCNuEr7U+obU+ZXQcY3WduO8Dfq+17tVaVwJngZLARhdWSoCzWutzWus+4Pd4n2MxSbTWbwHNV918H/CM7+NngPUBDWoEw8QcNsI24Y8gXyl1SCm1Wyl1q9HBjFIWcHHQ59W+24LR15RSR3wvj4PqJfsgofR8Xk0D25VSB5RSjxodzBhN0VrXAfjeZxgcz2iFwt/0iEI64Sul3lBKHR3i7XpnanVArtZ6CfC/gd8qpRIDE7HXOONWQ9xmyBSrEeL/CTADWIz3uf6hETGOQtA8n+OwQmu9FG856qtKqZVGBxTmQuVvekQh3fFKa33nOH6mF+j1fXxAKfUhMBsI2MWv8cSN9ww0Z9Dn2UDt5EQ0NqONXyn1H8Arfg5nvILm+RwrrXWt732DUuoFvOWpoa5VBaN6pdQ0rXWdUmoa0GB0QCPRWtf3fxzkf9MjCukz/PFQSqX3X+xUShUAs4BzxkY1Ki8Bn1ZKRSul8vHGvc/gmK7h+yfudz/ei9DBaD8wSymVr5SKwntB/CWDYxqRUipOKZXQ/zGwmuB9jofyEvCI7+NHgBcNjGVUQuhvekQhfYZ/PUqp+4EfAenAVqXUYa31GmAl8HdKKRfgBr6itQ6aizTDxa21PqaUehY4DriAr2qt3UbGOowfKKUW4y2PVAGPGRvO0LTWLqXU14BtgBX4pdb6mMFhjcYU4AWlFHj/f3+rtX7N2JCGppT6HbAKSFNKVQPfATYCzyqlvgRcAB4yLsJrDRPzqlD4mx4NWWkrhBAmYbqSjhBCmJUkfCGEMAlJ+EIIYRKS8IUQwiQk4QshhElIwhdCCJOQhC+EECYhCV8IIUzi/wPvRnAMFyD3fwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f3880a4ccc0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter([p.x for p in points], [p.y for p in points])\n",
    "plt.plot(*( pair for a, b in zip(answer, answer[1:]+answer[:1])\n",
    "                 for pair in [(a.x, b.x), (a.y, b.y)] ))\n",
    "plt.show()"
   ]
  }
 ],
 "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}

cool