{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "Given a set of points in the xy-plane, determine the minimum area of **any**\n",
    "rectangle formed from these points, with sides **not necessarily parallel** to\n",
    "the x and y axes.\n",
    "\n",
    "If there isn't any rectangle, return 0.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/12/21/1a.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[1,2],[2,1],[1,0],[0,1]]\n",
    "    Output: 2.00000\n",
    "    Explanation: The minimum area rectangle occurs at [1,2],[2,1],[1,0],[0,1], with an area of 2.\n",
    "\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/12/22/2.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[0,1],[2,1],[1,1],[1,0],[2,0]]\n",
    "    Output: 1.00000\n",
    "    Explanation: The minimum area rectangle occurs at [1,0],[1,1],[2,1],[2,0], with an area of 1.\n",
    "\n",
    "\n",
    "**Example 3:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/12/22/3.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[0,3],[1,2],[3,1],[1,3],[2,1]]\n",
    "    Output: 0\n",
    "    Explanation: There is no possible rectangle to form from these points.\n",
    "\n",
    "\n",
    "**Example 4:**\n",
    "\n",
    "![](https://assets.leetcode.com/uploads/2018/12/21/4c.png)\n",
    "\n",
    "\n",
    "\n",
    "    Input: [[3,1],[1,1],[0,1],[2,1],[3,3],[3,2],[0,2],[2,3]]\n",
    "    Output: 2.00000\n",
    "    Explanation: The minimum area rectangle occurs at [2,1],[2,3],[3,3],[3,1], with an area of 2.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Note:**\n",
    "\n",
    "  1. `1 <= points.length <= 50`\n",
    "  2. `0 <= points[i][0] <= 40000`\n",
    "  3. `0 <= points[i][1] <= 40000`\n",
    "  4. All points are distinct.\n",
    "  5. Answers within `10^-5` of the actual value will be accepted as correct."
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "min_area_free_rect (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "function min_area_free_rect(points::Vector{Vector{Int}})\n",
    "    function is_right_angle(p1, p2, p3)\n",
    "        return (p1[1] - p2[1]) * (p1[1] - p3[1]) + (p1[2] - p2[2]) * (p1[2] - p3[2]) == 0\n",
    "    end\n",
    "    point_set = Set(points)\n",
    "    res, len = Inf, length(points)\n",
    "    for i in 1 : len\n",
    "        for j in 1 + i : len\n",
    "            for k in 1 + j : len\n",
    "                flg = false\n",
    "                if is_right_angle(points[i], points[j], points[k])\n",
    "                    flg = true\n",
    "                elseif is_right_angle(points[j], points[k], points[i])\n",
    "                    flg = true\n",
    "                    i, j = j, i\n",
    "                elseif is_right_angle(points[k], points[i], points[j])\n",
    "                    i, k = k, i\n",
    "                    flg = true\n",
    "                end\n",
    "                if flg && (points[j] + points[k] - points[i]) in point_set\n",
    "                    area = sqrt(sum((points[i] - points[j]) .^ 2) * sum((points[i] - points[k]) .^ 2))\n",
    "                    (area > 0) && (res = min(res, area))\n",
    "                end\n",
    "            end\n",
    "        end\n",
    "    end\n",
    "    (res == Inf) ? 0.0 : res\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}