【每日一题】8月26日题目精讲

题号 NC110113
名称 Summer Earnings
来源 CF333E
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

n个点，任选其中三个为圆心作三个半径相同的圆，要求这三个圆不能相交（可以相切），求圆最大的半径是多少。
思路：任选三个点，圆的最大半径肯定是三个点当中距离最小的两个点的距离的一半。
考虑怎么来找到这三个点，直接暴力枚举点肯定不行，我们考虑把所有点的两两连出的边都求出来，然后从大到小排序，当我们从大到小遍历所有的边时，判断当前这条边连接的两个点是否已经在前面的边中和同一个点连上了（注意不是连上就可以，a和b连上了可能是a-c-d-b，这样是不算的），如果是，那就找到我们要找的三角形里面的最小边了。
我们怎么快速判断a和b是否连在了同一个点上呢？
对于每个点都开一个bitset，a点的bitset第i位为1，表示a已经和i连了边，那么我们把a和b的bitset做一个and运算，如果还有1存在，那么a和b之前就连过同样的点，此时的边a-b就是我们要求的三角形里面最短的那个边。

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目9月2日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴