178_Решающий_пень_Yandex_CodeRun_.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyNaUxFpIeBkZ+IQnvXWTVXs"
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "source": [
        "import sys\n",
        "\n",
        "n = int(sys.stdin.readline())\n",
        "xy = []\n",
        "right_n = 0\n",
        "sum_right = 0\n",
        "right_sse = 0\n",
        "for _ in range(n):\n",
        "    x, y = map(float, sys.stdin.readline().split())\n",
        "    xy.append([x, y])\n",
        "    sum_right += y\n",
        "    right_n += 1\n",
        "    b = sum_right / right_n\n",
        "    right_diff = y - b\n",
        "    right_sse += right_diff * (y - b)\n",
        "\n",
        "xy.sort()\n",
        "\n",
        "a = 0\n",
        "sum_left = 0\n",
        "left_n = 0\n",
        "left_sse = 0\n",
        "\n",
        "min_mse = right_sse\n",
        "\n",
        "min_c = xy[0][0]\n",
        "min_b = sum_right / right_n\n",
        "min_a = 0\n",
        "\n",
        "for i in range(len(xy) - 1):\n",
        "    cur_item = xy[i]\n",
        "    next_item = xy[i + 1]\n",
        "    c = (cur_item[0] + next_item[0]) / 2\n",
        "    sum_left += cur_item[1]\n",
        "    sum_right -= cur_item[1]\n",
        "    left_n += 1\n",
        "    right_n -= 1\n",
        "    left_diff = cur_item[1] - a\n",
        "    right_diff = cur_item[1] - b\n",
        "    a = sum_left / left_n\n",
        "    b = sum_right / right_n\n",
        "    left_sse += left_diff * (cur_item[1] - a)\n",
        "    right_sse -= right_diff * (cur_item[1] - b)\n",
        "    if cur_item[0] == next_item[0]:\n",
        "        continue\n",
        "\n",
        "    temp_mse = left_sse + right_sse\n",
        "    if temp_mse < min_mse:\n",
        "        min_mse = temp_mse\n",
        "        min_a, min_b, min_c = a, b, c\n",
        "\n",
        "print(min_a, min_b, min_c)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 211
        },
        "id": "w0WPIy0EO9ul",
        "outputId": "7d4a90bd-f81c-4883-a4d0-162361dbb47d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "error",
          "ename": "ValueError",
          "evalue": "invalid literal for int() with base 10: ''",
          "traceback": [
            "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
            "\u001b[0;31mValueError\u001b[0m                                Traceback (most recent call last)",
            "\u001b[0;32m<ipython-input-46-001722c7a307>\u001b[0m in \u001b[0;36m<cell line: 3>\u001b[0;34m()\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0msys\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mn\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0msys\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mstdin\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mreadline\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0mxy\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m[\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0mright_n\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
            "\u001b[0;31mValueError\u001b[0m: invalid literal for int() with base 10: ''"
          ]
        }
      ]
    }
  ]
}