※ 引述《chhsiao (bye~)》之铭言： : ※ 引述《sophialiege (爬回来了)》之铭言： : : 请问一下学长,Problem G该怎麽做? : : 我当初的想法是 : : 方案一 : : 先用一些gcd充分条件排掉一些不可能的解 : : 接下来,随机洒点,看看是否存在"可能"非必要的Expression : : 方案二 : : 用N-space的Convex Hull来解,不过很怕求点上precision的问题产生 : : 方案三 : : 用高斯消去法,依结果分析,不过初判是不可行 : : 之前没接触过这类型的题目,觉得很生疏,不知道是不是有Reference可以读? : 我们这一组有两个想法 : 第一个是对每一个 n 维超平面 : 看看可不可以在其他 m-1 条不等式的可行解区域截出截面 : 这样的话，这个超平面就是一个边界 : 方法找其他 m-1 个超平面与此超平面的交集 (是一个 n-1 维的次平面) : 看看这些次平面有没有解 : 也许先经过座标变换，让这个超平面变成 x = 0 会好解一点 : 不过 n 维的旋转... 不会 @@ n维旋转就像3维旋转那样 固定特定轴,做2维旋转,任何旋转都是这种旋转的合成 mathworld有不错的动态gif可以参考 : 另外一种方法是类似上面洒点的方法 : 可是取的点是任意其他 n 个方程式的交出来的点 : 也就是取所有的临界点 : 但是如果无解或无限多解, 还没有很明确的处理方式 : 不过两个都很烦，最後就随机洒点狂送 ^^| : (後来想我们也许我们取的座标的范围太窄了...) 可能要取一些floating的coordinate试试 春神说会有很近的lines且之间没有integer coordinate --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.250.175