题解：B4561 [合肥市小学组 2024 T3] 蛋糕识别

wangxy0311 · 2026-07-21 18:20:09 · 题解

题目传送门

题目大意

蛋糕顶点 (x,y)，是底边落在 x 轴上的等腰直角三角形。若存在另一块蛋糕 B，使得蛋糕 A 的顶点落在 B 三角形内部或边界上，则 A 无法被识别；若多个蛋糕拥有完全相同的坐标 (x,y)，全部无法识别。 求能被识别的蛋糕数量。

思路

已知蛋糕 A 坐标 (x_A,y_A)，蛋糕 B 坐标 (x_B,y_B)，如果想要让蛋糕 A 的顶点落在蛋糕 B 内部或边界，那么满足：

拆开不等式，得到：

把这个式子分成两个不等式，得：

• x_A−x_B+y_A \leq y_B
• −(x_A−x_B+y_A) \leq y_B

第一个式子移项可得：

第二个式子变形为：

最后移项得到：

我们设 X=x-y,Y=x+y，那么得到结论： 如果满足蛋糕 A 的顶点落在蛋糕 B 内部或边界，那么一定有\boldsymbol {X_B \leq X_A,Y_B \geq Y_A}。这里我们要让 X_B 更小或相等，Y_B 更大或相等。我们可以使用排序实现，比较逻辑是：如果 X_A \neq X_B，那么按照 X 从小到大排，反之按 Y 从大到小排。最后根据题目模拟即可。注意需要判断是否与左右邻居相同，相同就跳过。