Editing 0749 - Cerc 2

<code>N</code> puncte numerotate de la <code>1</code> la <code>N</code> sunt aşezate pe cerc, în sensul acelor de ceasornic, în ordine strict crescătoare.

Există <code>M</code> segmente de dreaptă diferite care unesc <code>M</code> perechi de puncte dintre cele <code>N</code> date. Cele două puncte care formează orice pereche sunt distincte.

Distanţele dintre două puncte succesive sunt alese astfel încât să nu existe <code>3</code> sau mai multe segmente care trec printr-un acelaşi punct interior cercului.

= Cerința =
Cunoscându-se numărul de puncte, numărul de perechi şi perechile de puncte care vor fi unite, se cere să se determine numărul <code>P</code> de puncte de intersecţie formate de acestea în interiorul cercului (punctele de intersecţie aflate chiar pe cerc nefiind luate în considerare).

= Date de intrare =
Fișierul de intrare <code>cerc2.in</code> conţine:

* pe prima linie două numere <code>N</code> şi <code>M</code> despărţite printr-un spaţiu, numere reprezentând numărul de puncte şi respectiv numărul de segmente;
* pe următoarele <code>M</code> linii, câte o pereche de numere distincte <code>p1[1]</code>, <code>p2[i]</code> despărţite prin câte un spaţiu, numere reprezentând capetele câte unui segment.

= Date de ieșire =
Fișierul de ieșire <code>cerc2.out</code> va conține un singur număr <code>P</code> reprezentând numărul total de puncte de intersecţie formate în interiorul cercului. Dacă acest număr depăşeşte <code>999999</code>, atunci se va scrie numărul format numai din ultimele sale <code>6</code> cifre.

= Restricții și precizări =

* <code>1 ≤ N ≤ 5000</code>
* <code>0 ≤ M < 125000</code>
* <code>1 ≤ p1[i] < p2[i] ≤ N</code>, numere naturale, oricare <code>i</code> din <code>{1,…, M}</code>
* NU există perechi <code>p1[i] p2[i]</code> identice.

= Exemplu: =
<code>cerc2.in</code>
 5 6
 1 2
 1 3
 1 4
 2 4
 3 5
 4 5
<code>cerc2.out</code>
 3

= Explicație =
S-au format în interiorul cercului <code>3</code> puncte de intersecţie (marcate prin cerculeţe pe figura de mai jos).

<syntaxhighlight lang="python" line="1">
def count_intersections(n, m, pairs):
    def intersects(a, b, c, d):
        return (a < c < b < d) or (c < a < d < b)
    
    intersections = 0
    
    # Iterate over all pairs of segments
    for i in range(m):
        for j in range(i + 1, m):
            a, b = pairs[i]
            c, d = pairs[j]
            # Ensure that for each segment (x, y), we have x < y
            if a > b:
                a, b = b, a
            if c > d:
                c, d = d, c
            if intersects(a, b, c, d):
                intersections += 1
    
    return intersections

# Citirea datelor de intrare
n = int(input("Introduceti numarul de puncte (N): "))
m = int(input("Introduceti numarul de perechi (M): "))
pairs = []

for _ in range(m):
    x, y = map(int, input().split())
    pairs.append((x, y))

# Calcularea numarului de puncte de intersectie
result = count_intersections(n, m, pairs)
print(f"Numarul de puncte de intersectie este: {result}")
</syntaxhighlight>