{"trustable":false,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"MD","content":"你想举办一个聚会。桌子上有一个多边形的蛋糕。你想把蛋糕切成几个三角形给受邀的客人吃。每个切割的轨迹都是一条线段,其两个端点是多边形的两个顶点。在多边形中,任意两个切割都应该是不相交的。当然,只有两个线段的端点相交的情况是允许的。\n\n蛋糕被认为是一个坐标系。你已经知道曲面的坐标了。每个切割都有一个与顶点坐标相关的成本,其公式为$cost_{i,j}\u003d|x_i+x_j|*|y_i+y_j|\\%p$。您要计算最小成本。\n\n注意:输入确保多边形蛋糕上没有三个相邻的顶点在一条线上。蛋糕并不总是凸多边形。\n\n输入\n\n有多组数据。两组数据之间有一个空行。每种情况的第一行包含两个整数,N和p(3≤N,p≤300),表示顶点的数量。接下来有N行包含两个整数$x,y(-10000\\leq x,y \\leq 10000)$,没有两个顶点在同一个坐标。\n\n输出:\n\n如果蛋糕不是一个凸多边形,输出“I can\u0027t cut.”。否则,输出最小花费。\n\n输入样例:\n\n~~~ \n3 3\n0 0\n1 1\n0 2\n~~~\n\n输出样例:\n\n~~~ \n0\n~~~\n\n"}}]}