2020-2021:teams:wangzai_milk:20200719_-_一些非常简单的计算几何扫描线题
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:20200719_-_一些非常简单的计算几何扫描线题 [2020/07/20 02:23] zars19 [POJ 3004 Subway planning] |
2020-2021:teams:wangzai_milk:20200719_-_一些非常简单的计算几何扫描线题 [2020/07/20 18:25] (当前版本) zars19 ↷ 页面名由2020-2021:teams:wangzai_milk:一些非常简单的计算几何扫描线题改为2020-2021:teams:wangzai_milk:20200719_-_一些非常简单的计算几何扫描线题 |
||
|---|---|---|---|
| 行 254: | 行 254: | ||
| 给二维平面上若干黑白点，要用一条直线划分，问一侧黑点加另一侧白点加线上点数目和的最大值。 | 给二维平面上若干黑白点，要用一条直线划分，问一侧黑点加另一侧白点加线上点数目和的最大值。 | ||
| - | 明显选其中两点连线是可以取到最大值的。枚举固定一点，极角排序，扫过去的同时维护一个半平面的区间即可。（实现技巧：把某个颜色的点变换为关于定点对称的点可以只数一侧点数便于统计；排序时用`atan2`判断是否在 $180°$ 内用叉积避免精度问题） | + | 明显选其中两点连线是可以取到最大值的。枚举固定一点，极角排序，扫过去的同时维护一个半平面的区间即可。（实现技巧：把某个颜色的点变换为关于定点对称的点可以只数一侧点数便于统计；排序时用''atan2''判断是否在 $180°$ 内用叉积避免精度问题） |
| <hidden><code cpp> | <hidden><code cpp> | ||
| 行 308: | 行 308: | ||
| 每个点都可以确定一个射线角度的区间，转化成区间覆盖问题（每个区间中至少要选一个点），贪心，因为是环形的，枚举每一个区间作为起始。（拓展阅读：[[https://www.cnblogs.com/I-Love-You-520/p/11147003.html|三类贪心区间覆盖问题 BY Ra煞]]） | 每个点都可以确定一个射线角度的区间，转化成区间覆盖问题（每个区间中至少要选一个点），贪心，因为是环形的，枚举每一个区间作为起始。（拓展阅读：[[https://www.cnblogs.com/I-Love-You-520/p/11147003.html|三类贪心区间覆盖问题 BY Ra煞]]） | ||
| - | 啊啊啊啊迷惑 $31$ 行到 $39$ 行这个部分我一开始用的`atan2`就不行。看别人的代码比对之后锁定问题就这段改成`asin`才能过。。 | + | 啊啊啊啊迷惑 $31$ 行到 $39$ 行这个部分我一开始用的''atan2''就不行。看别人的代码比对之后锁定问题就这段改成''asin''才能过。。 |
| <hidden><code cpp> | <hidden><code cpp> | ||
2020-2021/teams/wangzai_milk/20200719_-_一些非常简单的计算几何扫描线题.1595183008.txt.gz · 最后更改: 2020/07/20 02:23 由 zars19
