{"problem":{"name":"[SDCPC 2023] Computational Geometry","description":{"content":"Given a convex polygon $P$ with $n$ vertices, you need to choose three vertices of $P$, denoted as $a$, $b$ and $c$ in counter-clockwise order. There must be exactly $k$ edges from $b$ to $c$ in count","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9568"},"statements":[{"statement_type":"Markdown","content":"Given a convex polygon $P$ with $n$ vertices, you need to choose three vertices of $P$, denoted as $a$, $b$ and $c$ in counter-clockwise order. There must be exactly $k$ edges from $b$ to $c$ in counter-clockwise order (that is to say, $a$ is not an endpoint of these $k$ edges).\n\nConsider cutting through $P$ with segment $ab$ and $ac$. Let $Q$ be the polygon consisting of $ab$, $ac$ and the $k$ edges between $b$ and $c$. It's easy to see that this polygon has $(k + 2)$ edges.\n\nFind the maximum possible area of $Q$.\n \nNote that $ab$ and $ac$ can overlap with edges of $P$.\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $k$ ($3 \\le n \\le 10^5$, $1 \\le k \\le n-2$) indicating the number of vertices of the convex polygon $P$ and the number of edges from $b$ to $c$ in counter-clockwise order.\n\nFor the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \\le x_i, y_i \\le 10^9$) indicating the $x$ and $y$ coordinate of the $i$-th vertex of the convex polygon $P$. Vertices are given in counter-clockwise order. It's guaranteed that the area of the convex polygon is positive, and there are no two vertices with the same coordinate. It's possible that three vertices lie on the same line.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.\n\n## Output\n\nFor each test case output one line containing one real number indicating the maximum possible area of $Q$. Your answer will be considered correct if its relative or absolute error is less than $10^{-9}$.\n\n[samples]\n\n## Note\n\nFor the first sample test case, $Q$ is the whole triangle. Its area is $0.5$.\n\nThe second and third sample test case are shown below.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/vwd5087f.png)\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/twyillv0.png)","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9568","tags":["计算几何","2023","山东","Special Judge","O2优化","凸包","省赛/邀请赛"],"sample_group":[["3\n3 1\n0 0\n1 0\n0 1\n8 3\n1 2\n3 1\n5 1\n7 3\n8 6\n5 8\n3 7\n1 5\n7 2\n3 6\n1 1\n3 1\n7 1\n8 1\n5 6\n4 6\n","0.500000000000\n26.500000000000\n20.000000000000\n"]],"created_at":"2026-03-03 11:09:25"}}