sqr

set4

其实三道题都是水题,t1计算几何一个经典题,自行百度,t2单调栈。

这里讲一下第三题。

评讲的时候有人给出了扫描线线段树的做法。。。

然后我觉得有点麻烦,这里给出我的做法。。。

容易想到共同的一步,先旋转坐标系45°,但是这一步我们考虑到会出现小数,

但是sin45°有个很好的性质就是sin45°等于cos45°,那么考虑我们将坐标系扩大\frac{\sqrt{2}}{2}倍。

此时坐标系内点均处于整点,数据范围变为[-1200 *\sqrt{2},1200*\sqrt{2}]是能处理的。

然后记录正方形端点对应修改,最后递推求出每个点被多少矩形覆盖,然后就是O(1)查询

Tips:注意会出现负数,那么对于每个数加上负数最大值即可。

c++代码如下:

 

1 + 4 =