首页 > 其他分享 >CF607E Cross Sum

CF607E Cross Sum

时间:2024-01-16 20:23:34浏览次数:32  
标签:log dfrac Sum Cross 圆内 交点 mathcal 线段 CF607E

首先考虑把定点置换到原点,则直线方程变为 \(y + y_0 = \dfrac a{1000}(x + x_0) + \dfrac b{1000}\)。

令 \(k = \dfrac a{1000}, c = \dfrac{ax_0 + b}{1000} - y_0\),则有 \(y = kx + c\)。

考虑二分答案,找到一个最小的圆,使得圆内有至少 \(m\) 个交点,圆的半径 \(r\) 就是答案。

在圆内,每条直线就化为了弦,两条弦相交等价于它们所对的优弧相交,可以求出交点后做极角排序来把弦的端点离散化,这样弦就转化为了数轴上的线段,于是问题转化为数轴上有多少对相交线段,扫描线 + 树状数组就能解决。

具体来说,会产生贡献的两条线段 \(i, j\) 满足 \(l_i \le l_j \le r_i \le r_j\),我们把线段按 \(l\) 排序,然后再用树状数组处理剩下的 \(r\) 的偏序问题就好。

算贡献的时间复杂度是 \(\mathcal O(n \log n)\)。

最后推交点:

\[\begin{cases}{} y = kx + c \\ x^2 + y^2 = r^2 \end{cases} \]

把上面的 \(y\) 带到下面,整理一下就有 \((k ^ 2 + 1)x^2 + 2kcx + c^2 - r^2 = 0\)。

然后用笨蛋求根公式:

\[\Delta = 4k^2c^2 - 4(k^2 + 1)(c^2 - r^2) = 4(k^2r^2 + r^2 - c^2) \]

当 \(\Delta \ge 0\),也即 \(k^2r^2 + r^2 - c^2 \ge 0\) 时,直线与圆有交点,此时解得

\[x = \dfrac{-kc \pm \sqrt{k^2r^2 + r^2 - c^2}}{k^2 + 1} \]

再带回就能解 \(y\),也就解出了直线和圆的所有交点。

以上(找最小圆)的时间复杂度是 \(\mathcal O(n \log n \log V)\)。

接下来考虑如何计算答案。

把所有的合法交点分两类:恰在圆上的和圆内的。

  • 恰在圆上的距离就是半径了,直接加就好。
  • 对于在圆内的点,因为只有 \(\mathcal O(m)\) 个交点,所以直接开个 set 存前面线段的信息,暴力算交点求距离就好。

这样统计答案的时间复杂度就是 \(\mathcal O(m \log n)\)。

时间复杂度 \(\mathcal O(n \log n \log V + m \log n)\)。

简单算算就能发现极限数据下 \(m \log n \gg n \log n \log V\),耗时上计算答案占了大头,倒是前面找最小圆对耗时没啥影响,所以为了保证精度,多做几次二分罢~

标签:log,dfrac,Sum,Cross,圆内,交点,mathcal,线段,CF607E
From: https://www.cnblogs.com/chy12321/p/17968470

相关文章

  • CF1921F Sum of Progression
    题目链接:CF一道经典的类型题,把这种类型的题拿出来单独说一下。注意到问题中涉及到需要维护\(a_{x+k\timesstep}\)这样的信息,这样的信息很难用树型结构维护,比较容易用块级结构维护,我们注意到其实是每次这种步长\(+step\)的信息很难维护,我们考虑一类特殊的分块:如果\(step\)......
  • abc336 E - Digit Sum Divisible 题解 数位DP
    题目链接:https://atcoder.jp/contests/abc336/tasks/abc336_e题目大意:我们定义一个整数\(n\)的数位和为\(n\)的十进制表示中的各位上的数字之和。比如:整数\(2024\)的数位和为\(2+0+2+4=8\)。一个正整数\(n\)被称作一个好数如果\(n\)能被它的数位和整除......
  • PostgreSQL 数据库安全之检验数据块的损坏- data_checksums 参数设置
    默认情况下,数据页不受校验和保护,但可以选择为集群启用这一功能。启用后,每个数据页都包含一个校验和,该校验和在写入该页时更新,并在每次读取该页时进行验证。只有数据页受校验和保护;内部数据结构和临时文件不是。校验和通常在使用initdb初始化集群时启用。还可以在以后的脱......
  • 网络攻击技术(二)——Cross-site scripting
    网络攻击技术(二)——Cross-sitescripting 1.1.1摘要     在本系列的第一篇博文中,我向大家介绍了SQLInjection常用的攻击和防范的技术。这个漏洞可以导致一些非常严重的后果,但幸运的是我们可以通过限制用户数据库的权限、使用参数化的SQL语句或使用ORM等技术来防范......
  • 并行 sha256sum 命令
    之前为文件夹里的文件生成SHA-256摘要时,我使用的是sha256sum*.mp4*.xml*.jpg>sha256sums.txt这个命令是逐个生成哈希值的,在计算完成1.mp4之前并不会开始计算2.mp4,不能很好得利用多核性能。解决办法也很简单,利用“百闻不如一见”的xargs即可:echo*.mp4*.xml*.jp......
  • 关于函数式接口中常用的Supplier、Consumer、predicate、Function的总结以及其使用场
    首先介绍一下函数式接口:函数式接口在Java中是指:有且仅有一个抽象方法的接口。函数式接口,即适用于函数式编程场景的接口。而Java中的函数式编程体现就是Lambda,所以函数式接口就是可以适用于Lambda使用的接口。只有确保接口中有且仅有一个抽象方法,Java中的Lambda才能顺利地进行推导......
  • 测试SuspendThread、ResumeThread
    #include<iostream>#include<windows.h>#include<process.h>#include<conio.h>enum{ EVT_PAUSE=0, EVT_RESUME, EVT_QUIT, EVT_TOTAL};staticHANDLEevents[EVT_TOTAL]={NULL,NULL,NULL};staticunsignedint__stdcallhe......
  • CF1270G Subset with Zero Sum
    G.SubsetwithZeroSum很妙。一开始冲着背包去想的,显然不行。考虑他条件给的这个\(i−n\lea_i\lei−1\)化简一下得到\[1\lei-a_i\len\]题目要去求\[\sum\limits_{i\inS}a_i=0\]把所给信息往这个式子上靠。得到\[\sum\limits_{i\inS}i=\sum......
  • 天翼云亮相操作系统大会&openEuler Summit 2023,斩获多项大奖!
    近日,由开放原子开源基金会等主办,以“崛起数字时代引领数智未来”为主题的操作系统大会&openEulerSummit2023在北京举行。大会邀请院士、产业组织及全球开源基金会代表、学术领-袖、领先行业代表、技术专家等1000+位海内外嘉宾,共探操作系统产业发展方向和未来机遇。会上,天翼云......
  • 天翼云亮相操作系统大会&openEuler Summit 2023,斩获多项大奖!
    近日,由开放原子开源基金会等主办,以“崛起数字时代引领数智未来”为主题的操作系统大会&openEulerSummit2023在北京举行。大会邀请院士、产业组织及全球开源基金会代表、学术领袖、领先行业代表、技术专家等1000+位海内外嘉宾,共探操作系统产业发展方向和未来机遇。会上,天翼云荣获......