2020-2021:teams:wangzai_milk:20200527比赛记录
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/07 00:32] zars19 [A-Acperience] |
2020-2021:teams:wangzai_milk:20200527比赛记录 [2020/06/07 00:35] (当前版本) zars19 [E-Eureka] |
||
|---|---|---|---|
| 行 92: | 行 92: | ||
| 二维平面上给出$n$个点的坐标。一个有$\text{best pair}$的集合是最好的$\text{best set}$，$f(u,v)=\sqrt{(x_u−x_v)^2+(y_u−y_v)^2}$，$g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}2$，当$u,v$对集合中所有$w$满足$f(u,v)≥g(u,v,w)$，它们是$\text{best pair}$。求$\text{best set}$数量。 | 二维平面上给出$n$个点的坐标。一个有$\text{best pair}$的集合是最好的$\text{best set}$，$f(u,v)=\sqrt{(x_u−x_v)^2+(y_u−y_v)^2}$，$g(u,v,w)=\frac{f(u,v)+f(v,w)+f(w,u)}2$，当$u,v$对集合中所有$w$满足$f(u,v)≥g(u,v,w)$，它们是$\text{best pair}$。求$\text{best set}$数量。 | ||
| - | 题解：对着那个柿子稍微化简一下会发现是求平面上在一条直线上的点集的数量，本来写了$O(n\log^2n)$极角排序，但卡常失败非常痛苦。后来用''map<pair<LL,LL>,int>''记录每个角度的点的个数，''pair<LL,LL>''利用$\text{gcd}$避免精度问题，细节上需要一点排列组合。 | + | 题解：对着那个柿子稍微化简一下会发现是求平面上在一条直线上的点集的数量，本来写了$O(n\log^2n)$极角排序，但卡常失败非常痛苦。后来用''map<pair<LL,LL>,int>''记录每个角度的点的个数，''pair<LL,LL>''利用gcd避免精度问题，map写法比较微妙，不用多次排序常数好了很多。细节上需要一点排列组合处理。 |
| code: | code: | ||
2020-2021/teams/wangzai_milk/20200527比赛记录.1591461176.txt.gz · 最后更改: 2020/06/07 00:32 由 zars19
