Overlapping Disks

Overlapping Disks

Simple+
DE EN FR PL UK 简体中文

给定在二维平面上以图元表示的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)]:

example

输入: 列表 (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),
       ...
You should be an authorized user in order to see the full description and start solving this mission.
Settings
Code:
Other:
Invalid hot key. Each hot key should be unique and valid
Hot keys:
CheckiO Extensions

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.

Pair Programming (Beta-version)

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!

Waiting for Pair Programming to start...

You are trying to join a pair programming session that has not started yet.

Please wait for the session creator to join.

Waiting for Pair Programming to reconnect...

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.

×
 
 
<< <
> >>
exec show

Whats Next?

Free accounts will see Best CheckiO solutions with some delay.
Best Solutions will be opened in a moment
Become Awesome and Don't wait
The next stage is ""
Will be activated in
View More Solutions Random Review Solutions Go to the next mission