还想着复赛来试试精确做法 😄

在 Windows 环境下对 Checker.exe 进行反汇编分析，梳理出函数 IsSeperated 的核心执行逻辑：将两个多边形的顶点坐标乘以 1e6 后强制转换为整数，最终转换为 ClipperLib::IntPoint 类型；调用 ClipperLib::ClipperBase::AddPath 和 ClipperLib::Clipper::Execute 函数，在整数坐标系下计算两个多边形的布尔交集；将计算结果转回普通浮点数格式，通过叉乘法计算交集面积；按照公式判断多边形是否相交并返回结果：面积<min⁡(10−8, min⁡(areaA, areaB)×0.001)面积 < \min(10^{-8},\ \min(areaA,\ areaB) \times 0.001) 面积<min(10−8, min(areaA, areaB)×0.001)这里 ClipperLib 是一个第三方库，在整数坐标下处理多边形的布尔操作。造成问题的关键就是转整数这一步，暴力取整会导致本来很小的误差被大幅放大，达到 10−610^{-6}10−6 级别。

公平性 BUG（windows+linux双平台验证）! Checker重叠判定受IEEE 754双精度浮点舍入影响导致误判严重程度：高。 该bug导致数学上完全正确的最优MTV被误判为wrong，使得正确算法获得不公平的扣分。选手无法通过任何算法改进规避此问题——唯一的"修复"是故意输出非最优解（MTV偏长），这违背了题目"最小平移向量"的本意，且会导致其他case的准确度得分下降， 如果自己再进行校验会显著提升时间复杂度，是完全不公平的设计。该问题与选手代码无关，纯粹是Checker内部的浮点精度判定问题。 根据IEEE 754双精度浮点标准（IEEE Std 754-2019），十进制小数如-0.06463在二进制浮点中无法精确表示，加法运算结果的最低有效位存在不可避免的舍入（Round-to-nearest, ties-to-even）。Checker在10⁻¹⁷精度级别上依赖浮点加法结果进行重叠判定，超出了双精度浮点的可靠精度范围，属于判定逻辑缺陷。问题描述根据赛题规则，"重叠"指两个多边形有面积重叠（交集面积>0），而边重合（两个多边形共享边界线段但交集面积=0）是允许的、不算重叠的。这在赛题Checker的正常case中也能正确判定——大量边重合的case被正确判为correct。然而当MTV恰好使移动后的多边形B与多边形A边重合时，Checker在某些查询点上将合法的边重合误判为面积重叠（wrong），而在数学上完全等价的其他查询点上正确判为correct。误判的原因是Checker内部使用双精度浮点计算query + mtv时，舍入方向因查询点坐标的二进制表示而异：向下舍入时，本应边重合的情况被错误地计算为有极微小的面积重叠（~10⁻¹⁷级别）；向上舍入或精确时则正确判定为边重合（无面积重叠）。最小可复现用例输入文件 bug_test.in4 4 0.00000 0.00000 1.00000 0.00000 1.00000 0.08603 0.00000 0.08603 0.00000 0.00000 0.30850 0.00000 0.30850 0.21721 0.00000 0.21721 6 0.14778 -0.06463 0.50000 -0.06463 0.50000 -0.06250 0.50000 -0.05000 0.50000 -0.03125 0.50000 0.00000 多边形A：矩形 (0,0)-(1,0)-(1,0.08603)-(0,0.08603)多边形B：矩形 (0,0)-(0.30850,0)-(0.30850,0.21721)-(0,0.21721)6个查询点，x坐标在A内，y坐标从-0.06463到0.00000正确的MTV输出所有6个点的最短MTV方向都是向上（y方向），目标是将B的下边推到与A的上边对齐（y=0.08603）：6 0.00000 0.15066 0.00000 0.15066 0.00000 0.14853 0.00000 0.13603 0.00000 0.11728 0.00000 0.08603 数学验证6个查询点移动后的y坐标在数学上完全相同：点query_ymtv_yquery_y + mtv_y（数学精确值）0-0.064630.15066-6463/100000 + 15066/100000 = 8603/1000001-0.064630.15066同上 = 8603/1000002-0.062500.14853-6250/100000 + 14853/100000 = 8603/1000003-0.050000.13603-5000/100000 + 13603/100000 = 8603/1000004-0.031250.11728-3125/100000 + 11728/100000 = 8603/10000050.000000.086030 + 8603/100000 = 8603/100000移动后B的下边与A的上边共享水平线段 y=0.08603，重叠面积严格为0。所有6个点的输出都应判为correct。Checker结果#correct: 4, #total: 6 点0和点1被判wrong，点2~5被判correct。根因分析6个查询点的y坐标在IEEE 754双精度浮点中的加法行为：点0: -0.06463 + 0.15066 = 0.08603 - 1.39e-17 ← 向下舍入 → WRONG 点1: -0.06463 + 0.15066 = 0.08603 - 1.39e-17 ← 向下舍入 → WRONG 点2: -0.06250 + 0.14853 = 0.08603（精确） ← -0.0625 = -1/16，二进制精确 → OK 点3: -0.05000 + 0.13603 = 0.08603 + 1.39e-17 ← -0.05 = -1/20，舍入向上 → OK 点4: -0.03125 + 0.11728 = 0.08603（精确） ← -0.03125 = -1/32，二进制精确 → OK 点5: 0.00000 + 0.08603 = 0.08603（精确） → OK -0.06463不是二进制精确可表示的数（其二进制表示为无限小数）。与0.15066相加时，最低有效位向下舍入，导致双精度结果比数学精确值0.08603小1.39×10⁻¹⁷。Checker在此精度级别（10⁻¹⁷）上判定B的底边仍在A的顶边下方，从而认为存在重叠。同一组多边形、同一个NFP边界、数学上等价的MTV，仅因为查询点坐标的二进制表示差异，导致判定结果不同。这不符合预期。影响范围仅在两个多边形的长边平行时触发（矩形×矩形最典型）仅在MTV恰好为整5位小数时触发（移动后精确对齐边界）仅在查询点坐标不是二进制精确可表示数时触发练习赛 practice_1 中有7个查询点受此影响（9993/10000）复现环境已在以下两个环境分别验证，结果完全一致（#correct: 4, #total: 6）：Windows 10 Pro：GCC 15.2 (MSYS2 MinGW64) + 赛题提供的 Windows 版 Checker/RunnerUbuntu 24.04 (WSL)：GCC 11.4.0 + 赛题提供的 Linux 版 Checker/Runner复现步骤# 1. 创建输入文件 bug_test.in（内容如上） # 2. 选手程序输出 MTV: # (0,0.15066) (0,0.15066) (0,0.14853) (0,0.13603) (0,0.11728) (0,0.08603) # 3. Checker判定 Checker.exe bug_test.in output.out output.out # 结果: #correct: 4, #total: 6 （点0和点1被误判为wrong） # 4. Python验证浮点加法方向 python -c "print(-0.06463 + 0.15066 - 0.08603)" # -1.39e-17 (向下) python -c "print(-0.05000 + 0.13603 - 0.08603)" # +1.39e-17 (向上) python -c "print(-0.06250 + 0.14853 - 0.08603)" # 0.0 (精确) 进一步验证：Checker面积判定行为使用同一组多边形，固定查询点 (0.50000, 0.00000)（浮点精确数），手动构造不同MTV测试Checker判定：MTV_y移动后y理论重叠面积Checker0.086000.086009.26×10⁻⁶wrong ✗0.086020.086023.08×10⁻⁶wrong ✗0.086030.086030（边重合）correct ✓0.086040.086040（已分离）correct ✓Checker使用面积法判定重叠，面积阈值极小（接近0）。精确边重合（面积=0）正确判为correct。但当浮点加法舍入让query(-0.06463) + mtv(0.15066)的结果偏小1e-17时，本应面积为0的边重合被Checker误判为有面积重叠。理论虚假面积：坐标偏差(10⁻¹⁷) × 重叠宽度(0.3085) ≈ 3×10⁻¹⁸。但Checker内部使用叉积公式计算多边形交集面积时，计算精度本身只到10⁻¹⁷级别（顶点坐标量级0.1~0.5，叉积误差≈坐标²×机器精度≈10⁻¹⁷），可能将理论为0的面积计算出一个高于判定阈值的噪声值。建议修复根据赛题规则，重叠判定条件为面积 < min(1e-8, min(areaA, areaB) * 0.001)。建议确认Checker实现中：面积阈值是否正确生效：本例中阈值应为 min(1e-8, 0.067×0.001) = 1e-8，理论虚假面积~3×10⁻¹⁸远小于此阈值，不应判wrong面积计算精度是否足够：如果Checker的多边形交集面积计算本身存在浮点误差放大（如先做裁剪再算面积），可能将~0的面积计算为一个远大于实际的值如阈值已正确设置，建议检查面积计算路径是否存在浮点误差放大，或在面积比较前增加一层绝对容差保护（如面积 < max(阈值, 10⁻¹⁰) 视为不重叠）。

能不能给出官方的baseline呀，哪怕是实现方案也可以呀，不然完全摸瞎，不知道优化啥

初衷竟然只是为了防止开挂。。反正也是单核

同样一套代码提交能相差四万多分这个还是考察算法的实力吗谁运气好谁分高呗，公平性在哪，我希望主办方就此问题做出解释我应该怎样区分我的代码到底是因为算法质量提分还是因为判题器数据集运气好提分的

Checker 程序的运行参数有一个answer_file，是正确的答案文件，但是现在答案文件去哪里搞。初赛练习的数据集都找不到了

请问主办方是如何判断两个图形重叠的？边重叠算不算重叠？顶点重叠算不算重叠？顶点和边重叠算不算重叠？因为输出数据精度的问题，去尾或四舍五入之后有极小范围重叠算不算重叠？或者多大面积以内算重叠？

如图，同一份代码，四舍五入的情况下保留5位数输出比保留6位数分数还高

难道这么简单的多文件都能卡出贵赛方的bug吗

我现在是10ms左右，但是一直是33300分，我看前面有人说正确性满分就是这个，那效率分到底得多快才能算分

练习和正式比赛是随机挑一组测评数据还是多组测评数据取平均算得分

昨晚九点多提交的，今早一看还在评分中，是用cpp写的

我提交了官方的Solution.cpp，想测试一下提交代码的流程。但是一直显示编译失败，请问是什么原因呢？

不然根本不知道自己的分应该优化正确性还是速度，优化了交上去都没有提示，作为练习赛，应该放开这一点吧