[THUPC 2022 初赛] 喵喵花園

Luogu
IDLGP8212
Time8000ms
Memory512MB
DifficultyP6
计算几何2022Special JudgeO2优化模拟退火THUPC
喵喵是一只非常富有的猫咪,他在海淀区拥有一个大花园。 这个大花园是由一些旧栅栏为边界所形成的 $N$-gon(即具有 $N$ 边的多边形)。 由于圣诞节快到了,喵喵想用 $K$ 棵圣诞树来装饰一下花园。 同时,喵喵坚信找到一些好的位置来种树会给他带来好运。 作为一只好猫咪,他决定寻找最佳位置如下: - 所有的树都应该在花园的边界上。 - 这些 $K$ 树应该平均划分花园的周长。 - 由树木形成的新凸面$K$-gon 的面积应尽可能小。 虽然喵喵比你有钱,但他没有你那么聪明。 因此,他给了你一些钱,让你帮他找出凸$K$-gon 的最小面积。 ## Input 第一行包含两个整数,$N$ 和 $K$,代表原本花园边界的顶点数和树的数量。 接下来的每行 $N$ 行包含两个整数 $x_i$ 和 $y_i$,表示花园边界顶点的坐标。 所有座标均为逆时针给出的。 ## Output 输出凸面 $K$-gon 的最小面积。 如果相对或绝对误差不超过 $10^{-8}$,则您的答案被认为是正确的。 [samples] ## Note 【数据范围】 - $3 \le N, K \le 1000$; - $-10^5 \le x_i, y_i \le 10^5$。
Samples
Input #1
5 4
0 0
1 0
2 1
2 2
0 2
Output #1
1.9892766953
Input #2
3 3
0 0
1 0
0 1
Output #2
0.1226170434
API Response (JSON)
{
  "problem": {
    "name": "[THUPC 2022 初赛] 喵喵花園",
    "description": {
      "content": "喵喵是一只非常富有的猫咪,他在海淀区拥有一个大花园。 这个大花园是由一些旧栅栏为边界所形成的 $N$-gon(即具有 $N$ 边的多边形)。 由于圣诞节快到了,喵喵想用 $K$ 棵圣诞树来装饰一下花园。 同时,喵喵坚信找到一些好的位置来种树会给他带来好运。 作为一只好猫咪,他决定寻找最佳位置如下: - 所有的树都应该在花园的边界上。 - 这些 $K$ 树应该平均划分花园的周长。 - 由树木",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8212"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "喵喵是一只非常富有的猫咪,他在海淀区拥有一个大花园。\n\n这个大花园是由一些旧栅栏为边界所形成的 $N$-gon(即具有 $N$ 边的多边形)。\n\n由于圣诞节快到了,喵喵想用 $K$ 棵圣诞树来装饰一下花园。 同时,喵喵坚信找到一些好的位置来种树会给他带来好运。\n\n作为一只好猫咪,他决定寻找最佳位置如下:\n\n- 所有的树都应该在花园的边界上。\n- 这些 $K$ 树应该平均划分花园的周长。\n- 由树木...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments