![](../../asset/images/user/bgImg_default.jpeg)
简介
该用户还未填写简介
擅长的技术栈
未填写擅长的技术栈
可提供的服务
暂无可提供的服务
计算几何系列 —— 扫描线算法
显然,只要一条线段被覆盖,那么它肯定被图形所截。所以,整个问题就转化为了一个区间查询问题,即:每次将当前扫描线扫到的边对应的信息按照之前赋上的权值更新,然后再查询线段树根节点的信息,最后得到当前扫描线扫过的面积。这就可以用线段树来实现了(线段树:顾名思义,就是树上的结点为一条条线段~),接下来我们来简单看一下模拟过程:
![文章图片](https://img-blog.csdnimg.cn/direct/51b3d488df36439d9acff47a905ac698.png)
2023 ICPC 亚洲区域赛南京站计算几何 —— Problem B.交并比(源代码出炉+解析)
2.两个矩形的相交面积比上面积并就是所谓的交并比(IOU);1.给定一个矩形(OBB),要求找到一个坐标轴平行矩形(AABB);3.我们需要求出这个矩形使IOU最大。博客👆中,我们通过非常复杂的代数方法证明关于IOU的这个函数是。三分法,爬山法,梯度下降法。
![文章图片](https://img-blog.csdnimg.cn/direct/b27a3404e21447859701e1bb459fbc3b.png)
到底了