![Overlapping Disks](https://d17mnqrx9pmt3e.cloudfront.net/media/logos/task/middle/overlapping-disks-unsolved.png)
Overlapping Disks
给定在二维平面上以图元表示的disks
的列表 (x, y, r)
使x, y
为圆心点,r
为该圆盘的半径,请计算有多少对圆盘相交。
两个圆盘 (x1, y1, r1)
和 (x2, y2, r2)
相交,当且仅当它们满足毕达哥拉斯不等式(x2-x1)**2+(y2-y1)**2<=(r1+r2)**2
时。
请注意,只要参数是整数,这个精确的公式就能在纯粹的整数运算中运行,因此没有平方根或任何其他无理数的小数噪音。(该公式还使用运算符<=
将两个接吻盘视为相交的一对)。
对于这个问题,简单地循环所有可能的磁盘对是可行的,但对于大型列表来说,效率会变得非常低。然而,sweep line algorithm 不仅能有效地解决这个问题,而且还能高效地解决这个问题(这是一个至关重要但经常被忽视的 "效率 "区别),因为它只需查看少得多的磁盘对。
下面是一个 [(0, 0, 3), (6, 0, 3), (6, 6, 3), (0, 6, 3)]
:
输入: 列表 (List)元组 (tuple)的整数 (int).
输出:整数 (int).
示例
assert overlapping_disks([(0, 0, 3), (6, 0, 3), (6, 6, 3), (0, 6, 3)]) == 4 assert overlapping_disks([(4, -1, 3), (-3, 3, 2), (-3, 4, 2), (3, 1, 4)]) == 2 assert ( overlapping_disks([(-10, 6, 2), (6, -4, 5), (6, 3, 5), (-9, -8, 1), (1, -5, 3)]) == 2 ) assert ( overlapping_disks( [ (2, 2, 1), (3, 3, 1), (4, 4, 2), (5, 5, 2), (6, 6, 3), (7, 7, 3), (8, 8, 4), (9, 9, 4), (10, 10, 5), ...
CheckiO Extensions allow you to use local files to solve missions. More info in a blog post.
In order to install CheckiO client you'll need installed Python (version at least 3.8)
Install CheckiO Client first:
pip3 install checkio_client
Configure your tool
checkio --domain=py config --key=
Sync solutions into your local folder
checkio sync
(in beta testing) Launch local server so your browser can use it and sync solution between local file end extension on the fly. (doesn't work for safari)
checkio serv -d
Alternatevly, you can install Chrome extension or FF addon
checkio install-plugin
checkio install-plugin --ff
checkio install-plugin --chromium
Read more here about other functionality that the checkio client provides. Feel free to submit an issue in case of any difficulties.
Welcome to Pair Programming! Engage in real-time collaboration on coding projects by starting a session and sharing the provided unique URL with friends or colleagues. This feature is perfect for joint project development, debugging, or learning new skills together. Simply click 'Start Session' to begin your collaborative coding journey!
You are trying to join a pair programming session that has not started yet.
Please wait for the session creator to join.
It looks like the creator of the pair programming session closed the editor window.
It might happen accidentally, so that you can wait for reconnection.