{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最小圆问题\n",
    "\n",
    "**类别：** 选址\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/smallest-circle-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**Smallest Circle Problem**（也称为 Minimum Covering Circle Problem 或 Smallest Enclosing Circle Problem）是一个计算几何问题，其目的是在欧几里得平面上计算包含给定点集的最小圆。\n",
    "\n",
    "该问题是一个 [Facility Location Problem](https://optagent.pages.dev/examples/location/facility_location_problem_flp/)（1-Center Problem）的实例，其中需要为新设施选择一个位置，以便为多个客户提供服务，并最小化任何客户到达该新设施所需的最远距离。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用 OptAgent 的 `float` 决策变量建模圆心坐标\n",
    "- 使用非线性算子 `sqrt` 和幂运算计算圆的半径\n",
    "- 区分圆心决策变量与由圆心推导出的半径表达式\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "数据文件的格式如下：\n",
    "\n",
    "- 第一行：点的数量\n",
    "- 接下来几行：对于每个点，其 x 和 y 坐标\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "Smallest Circle Problem 的 OptAgent 模型使用两个 `float` 决策变量分别表示圆心的横坐标和纵坐标。通过 `sqrt`、`max` 和幂运算，将半径计算为圆心到所有给定点距离的最大值。半径可由圆心坐标推导，因此只是中间表达式，不需要额外的决策变量。\n",
    "\n",
    "目标函数是最小化圆的半径。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    return [int(value) for value in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "\n",
    "\n",
    "def read_instance(instance_file):\n",
    "    values = iter(read_integers(instance_file))\n",
    "    nb_points = next(values)\n",
    "    return [(next(values), next(values)) for _ in range(nb_points)]\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=6):\n",
    "    points = read_instance(input_file)\n",
    "    coord_x = [point[0] for point in points]\n",
    "    coord_y = [point[1] for point in points]\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # The circle center lies within the points' coordinate bounds.\n",
    "    x = model.float(min(coord_x), max(coord_x))\n",
    "    y = model.float(min(coord_y), max(coord_y))\n",
    "\n",
    "    # The radius is the maximum Euclidean distance from the center.\n",
    "    squared_distances = [(x - point_x) ** 2 + (y - point_y) ** 2 for point_x, point_y in points]\n",
    "    radius = model.sqrt(model.max(squared_distances))\n",
    "    model.minimize(radius)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible circle found; Status = {solution.status}\")\n",
    "        return solution\n",
    "\n",
    "    result_text = f\"x={x.value:.6f}\\ny={y.value:.6f}\\nr={radius.value:.6f}\"\n",
    "    print(f\"Status = {solution.status}\\n{result_text}\")\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(result_text + \"\\n\", encoding=\"utf-8\")\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "Notebook 直接调用 `main` 并显式传入点集实例路径。以下代码格相互独立，可以按需要单独运行；调整 `time_limit` 可以控制每个实例的求解时间。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_10points = main(\n",
    "    INSTANCE_DIR / \"10points.txt\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_20points = main(\n",
    "    INSTANCE_DIR / \"20points.txt\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_30points = main(\n",
    "    INSTANCE_DIR / \"30points.txt\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}