101911l专题

Gym 101911L Ray in the tube(思维题)

原题地址 题意:给出两根线,每根线上有若干个传感器,你可以选择任意一条射线,这条射线会在两根线内不断折射,求经过的最多的传感器数量 思路: 可以发现在每个传感器的地方,我们并不要枚举每一个角度,观察上面的图可以发现,我们只需要枚举log条射线就可以覆盖所有的情况。 那么现在的问题就是如何快速求出每一条射线覆盖的传感器的数量。 假设枚举的射线的长度是len(就是一条折射的射线上在一条直线上相邻