题解 P3108 【[USACO14OPEN]Cow Optics G】

· · 题解

题解 P3108 【Cow Optics G】

没看过题的同学请走着（传送门）

首先这光线必须竖直或水平。~~（不然这题目还能做？） ~~

实际上我们从谷仓的位置向四个方向射出光线，并从原点射出光线，它们的交点就是我们要求的答案位置。

那么我们可以知道，如果一条原点出发的能到达的边与从谷仓出发能到达的边有交点，那么在交点放一面镜子，我们就能够使光线到达谷仓。

如图：

原谅画的比较差

然后用扫描线X轴，Y轴扫一下就好了（所以代码过程要处理两次）