初めに、二次元平面上の $2$ つの線分 $AB,CD$ が(端点以外で)交差するかを判定する方法を考えます。 $A(x_A,y_A),B(x_B,y_B),C(x_C,y_C),D(x_D,y_D)$ とします。
ここで、端点以外で交差する必要十分条件は以下の $2$ つを共に満たすことです。

• 直線 $AB$ で平面を分割するとき $C,D$ が別の領域に存在
• 直線 $CD$ で平面を分割するとき $A,B$ が別の領域に存在

$1$ つめの条件を判定する方法を考えます。直線 $AB$ の方程式は $(x_A-x_B)(y-y_A)-(y_A-y_B)(x-x_A)=0$ なのでこれの $(x,y)$ に $(x_C,y_C),(x_D,y_D)$ を代入したときの符号が異なればよいです。
$2$ つめの条件も同様に判定できるので $O(1)$ で判定できます。

ワーシャルフロイド法を適用することを考えます。考慮するべき点は警備員のいる点、建物の角の点、不審物の点で十分です。 $N=a+4b+c$ とします。
ある点からある点まで直接行けるかは建物の四辺と対角線と交差しなければよく、 $2$ つの点ごとに $O(b)$ で判定できるので、一直線に行ける分の反映は $O(N^2b)$ で可能です。
ワーシャルフロイドは $O(N^3)$ で可能です。

結局、この問題を \(O(N^3)\) で解くことができました。なお、ダイクストラでも問題ないです。