题目链接 Grab the Seat!
Hint1：考虑每个学生会挡住的范围是什么
Hint2：对于每个学生挡住的范围我们都要考虑吗，哪些学生可以根本不用考虑。
以题中最左上的学生为例，学生遮住的范围可以见下图，可以发现细线范围内（包括边界）的所有点与红点连线都会与黑板有焦点，所以这个范围内的点都是不可行的
这个范围可以是与黑板的端点连线夹成的区域，可以通过画图比较清晰的发现，同一行的点可以只考虑最左边端的点，同一行的其他点遮住的范围一定在这一行中最左端的点遮住范围内。
对于每一行的一个点我们都可以得到一个这样的夹角，对于这些夹角的两条边我们可以分成两组，上面的边分成一组，向下的分成一组。
先以向上的边为例，可以发现他们都有同样的方程
如果只看同一行的点的被覆盖情况，斜率越大的直线能遮挡的越多
所以我们可以按照学生位置的纵坐标从小到大遍历一遍（第一行比较特殊不用处理），对于一个新插入的点（即代表的一个直线）如果斜率大于之前的斜率那么完全可以只考虑新插入的这条直线的覆盖情况，否则这条新插入的直线可以不考虑他的影响，然后对新处理出的直线求与当前行的交点坐标，因为是整数点所以需要向上取整，即可得到对当前行的覆盖情况，对于每一行都进行同样的操作，向下的直线同理。
求交点其实就是把方程 解一下即可
京公网安备 11010502036488号