Editing 0950 - Cerc 3

== Enunț ==
Se consideră pe axa <code>Ox</code> din plan n puncte distincte reprezentând centrele a <code>n</code> cercuri numerotate cu numerele distincte de la <code>1</code> la <code>n</code>. Pentru fiecare cerc <code>k</code> se cunosc abscisa <code>xk</code> a centrului său şi raza sa <code>rk</code>.

= Cerința =
Să se scrie un program care să determine numărul <code>y</code> maxim de cercuri exterioare două câte două dintre cele <code>n</code>.

= Date de intrare =
Fișierul de intrare <code>cerc3IN.txt</code> conține pe prima linie pe prima linie, o valoare naturală n, reprezentând numărul de cercuri, iar pe următoarele n linii câte două numere naturale, separate printr-un spaţiu, care reprezintă abscisa <code>x1</code> a centrului primului cerc şi raza sa <code>r1</code>,…, abscisa <code>xn</code> a centrului celui de-al <code>n</code>-lea cerc şi raza sa <code>rn</code>.

= Date de ieșire =
Fișierul de ieșire <code>cerc3OUT.txt</code> va conține o linie pe care va fi scris numărul natural <code>y</code> reprezentând numărul maxim de cercuri exterioare ale căror centre sunt situate pe axa <code>Ox</code>. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* numerele <code>n</code>, <code>x1</code>,<code>x2</code>,…,<code>xn</code>, <code>r1</code>, <code>r2</code>,…, <code>rn</code> sunt numere naturale
* <code>1 ≤ n ≤ 300</code>
* <code>1 ≤</code>  <code>x1</code>,<code>x2</code>,…,<code>xn</code> <code>≤ 150</code>
* <code>1 ≤</code> <code>r1</code>, <code>r2</code>,…, <code>rn</code> <code>≤ 70</code>
* dacă două cercuri, dintre cele <code>n</code>, au centrele în acelaşi punct de pe axa <code>Ox</code>, atunci razele lor sunt distincte
* două cercuri sunt exterioare dacă nu au niciun punct comun şi nici interioarele lor nu au puncte comune

= Exemplul 1: =
<code>cerc3IN.txt</code>
 8
 3 1
 1 4
 8 1
 11 2
 15 2
 16 6
 21 2
 21 1
<code>cerc3OUT.txt</code>
 4

= Explicație =
Numărul maxim de cercuri exterioare două câte două este <code>y=4</code>.

== Exemplul 2: ==
<code>cerc3IN.txt</code>
 301
 3 1
 1 4
 8 1
 11 2
 15 2
 16 6
 21 2
 21 1
<code>cerc3OUT.txt</code>
 Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, cercuri):
    if n < 1 or n > 300:
        return False

    for x, r in cercuri:
        if x < 1 or x > 150 or r < 1 or r > 70:
            return False

    return True

def main():
    with open("cerc3IN.txt", "r") as f, open("cerc3OUT.txt", "w") as g:
        n_line = f.readline().strip()
        
        if not n_line:
            g.write("Datele din fisierul de intrare lipsesc sau sunt incomplete.")
            return

        try:
            n = int(n_line)
        except ValueError:
            g.write("Numarul de cercuri este invalid.")
            return

        cercuri = []
        for line in f:
            values = line.split()
            if len(values) != 2:
                g.write("Datele din fisierul de intrare sunt incomplete sau au format invalid.")
                return
            
            try:
                o, r = map(int, values)
            except ValueError:
                g.write("Coordonatele sau razele cercurilor sunt invalide.")
                return
            
            cercuri.append((o, r))

        if not verificare_restrictii(n, cercuri):
            g.write("Datele nu corespund restrictiilor impuse")
            return

        cercuri = [(o - r, o + r) for o, r in cercuri]
        cercuri.sort(key=lambda x: x[1])

        nr = 1
        x = cercuri[0][1]
        for i in range(1, n):
            if x < cercuri[i][0]:
                nr += 1
                x = cercuri[i][1]

        g.write(str(nr))

if __name__ == "__main__":
    main()

</syntaxhighlight>