0950 - Cerc 3

Enunț

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

Cerința

Să se scrie un program care să determine numărul y maxim de cercuri exterioare două câte două dintre cele n.

Date de intrare

Fișierul de intrare cerc3IN.txt 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 x1 a centrului primului cerc şi raza sa r1,…, abscisa xn a centrului celui de-al n-lea cerc şi raza sa rn.

Date de ieșire

Fișierul de ieșire cerc3OUT.txt va conține o linie pe care va fi scris numărul natural y reprezentând numărul maxim de cercuri exterioare ale căror centre sunt situate pe axa Ox. Î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 n, x1,x2,…,xn, r1, r2,…, rn sunt numere naturale
• 1 ≤ n ≤ 300
• 1 ≤  x1,x2,…,xn ≤ 150
• 1 ≤ r1, r2,…, rn ≤ 70
• dacă două cercuri, dintre cele n, au centrele în acelaşi punct de pe axa Ox, 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:

cerc3IN.txt

8
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1

cerc3OUT.txt

4

Explicație

Numărul maxim de cercuri exterioare două câte două este y=4.

Exemplul 2:

cerc3IN.txt

301
3 1
1 4
8 1
11 2
15 2
16 6
21 2
21 1

cerc3OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

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()