sol：P2586 [ZJOI2008] 杀蚂蚁

流水行船CCD · 2024-07-09 18:28:05 · 题解

link

思路

这题的其他部分大佬已经讲得很详细了，这题重点讲一下一种仅需要初中知识的圆和线段相交判定（不需要直线距离公式和三角函数，仅需要基础的相似和一次函数知识）。

• 坐标系原点为激光塔。
• 红色线段为激光。
• 红色线段第一象限内的端点是一只被攻击的蚂蚁。

首先，常规的一个半径为 0.5 的圆和图中红色线段相交的充要条件是其圆心在黑色轮廓线（两个黑色圆半径均为 0.5）内，但是黑色轮廓线有圆且不规则，较难求解。但是此题的要求给了我们一些特殊性质，可以特化求解。

• 性质一：所有要判断的圆心均为整点。

• 性质二：所有要判断的圆半径均为 0.5。

此时，由于黑色圆的半径只有 0.5，所以所有在绿色矩形以外的整点均不可能在黑色轮廓之中，因此我们需要判断的黑色轮廓线就简化为途中卡其色阴影部分，而卡其色阴影部分正是图中两黄色平行线之间和绿色矩形的交集。

于是只需要判断一个点是否同时在黄色平行线和绿色矩形之间即可。

矩形很好判断，但是判断一个点是否在平行线之间需要知道两平行线解析式。

• 斜率：它们的斜率 k' 就是原红色直线的斜率 k。

• 与 y 轴的交点：不难发现图中淡蓝色阴影直角三角形相似，而小直角三角形的长直角边为 0.5，大直角三角形三边已知，就可以求得小直角三角形斜边，即图中的棕色线段，而棕色线段的长度就是该平行线与 y 轴的交点。

至此，两平行线解析式已知，即可判断。

Code（部分）

inline bool damage(int x1, int y1, int x2, int y2, int x3, int y3) {//直线两端点为 (x1,y1) (x2,y2)，与圆心为 (x3,y3) 半径为 0.5 的圆是否相交 
    if (x3 < min(x1, x2) || max(x1, x2) < x3) return false; // 是否在矩形中 
    if (y3 < min(y1, y2) || max(y1, y2) < y3) return false; // 是否在矩形中 
    if (x1 == x2) return x1 == x3; // 特判直线竖直 
    if (y1 == y2) return y1 == y3; // 特判直线水平 
    double k = 1.0 * (y1 - y2) / (x1 - x2), b = 1.0 * y1 - 1.0 * k * x1; // 红色直线解析式 
    double dlt = sqrt((double)(x1 - x2) * (x1 - x2) + (double)(y1 - y2) * (y1 - y2)) * 0.5 / (max(x1, x2) - min(x1, x2)); // 棕色线段长度（相似） 
    double bup = b + dlt, bdown = b - dlt, x33 = x3, y33 = y3; // 上下平行线解析式  y = kx + bup, y = kx + bdown
    return x33 * k + bdown <= y33 && y33 <= x33 * k + bup; // 是否在平行线之间 
}