円形領域(Back Jun 10000-Python)

白俊で初めてやったプラチナ問題なので、何とかして解決しようと思います.一日中かかってやっと解けた...これはそんなに時間がかかる問題ではありませんが、いろいろな間違いを修正するのに時間がかかりすぎます.😢

質問する

x軸にはN個の円があります.円が交わらない.でも、触れることができます.
円の領域を計算するプログラムを作成してください.
領域は点の集合であり、すべての2点が交差しない円の連続曲線に接続されなければならない.

入力

第1行は円の個数N(1≦N≦300000)を与える.
次のN行では、各円の情報xiおよびriに整数が与えられる.xiは円の中心座標、riは半径です.(-109 ≤ xi ≤ 109, 1 ≤ ri ≤ 109)
入力された円は常に一意です.

しゅつりょく

最初の行は、円で生成された領域の個数を出力します.

入力例

2
1 3
5 1

サンプル出力

3

問題を解く

問題の条件から見ると、円は交差しない.
つまり、一つの円があれば、もう一つの円は
1.この円の中に
2.外で
3.いっそ掛けてくれ
この3つの状況しかありません.
したがって
大きな円の内側の円の端点がつながっていると
2つのスペースがありました.
そうでなければ.
空間が一体である
私は再帰でこの問題を解く.

ろんりじゅんじょ

ウォンの中心から半径を引いて、1ウォンの両端座標を2次元配列にして保存する.

ウォンの左座標は降順で、左座標が同じなら右座標は昇順である.
このように並べると、左から大きな順番で格納されます.

の各円を迂回して、その中の円の端点がつながっているかどうかを確認します.

の現在の円と次の円の左座標が同じ場合、次の円に関連する円が検索されます.

個のエンドポイントを接続すると、2つのスペースを増やすことができます.

コード#コード#

import sys
from bisect import  *
sys.setrecursionlimit(10**6)

num = int(input())
circles= []
ans =2
for _ in range(num):
    center , banji=  map(int,sys.stdin.readline().split())
    circles.append([center-banji , center +banji])

circles.sort( key= lambda x:( x[0], -x[1]))

def checking(start_int, end):
    if start_int == num:
        return 0
    elif circles[start_int][1]==end:
        return 1
    elif circles[start_int][1]!=end:
        tmp_int =bisect_left(circles,[circles[start_int][1],]) 
        if circles[tmp_int][0] is not None and circles[tmp_int][0] == circles[start_int][1]:
            return 1* checking(tmp_int,end)
        else:
            return 0
    else:
        return 0

for i in range(num-1):
    if circles[i][0] == circles[i+1][0]:
        if circles[i][1] == circles[i+1][1]:
            ans+=1
        else:
            start_int = bisect_left(circles,[circles[i+1][1],])
            if circles[start_int][0] == circles[i+1][1]:
                if checking(start_int, circles[i][1]) ==1:
                    ans +=2
                else:
                    ans +=1
            else:
                ans+=1
    else:
        ans +=1
print(ans)