0749 - Cerc 2

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

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

Distanţele dintre două puncte succesive sunt alese astfel încât să nu existe 3 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 P 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 cerc2.in conţine:

• pe prima linie două numere N şi M despărţite printr-un spaţiu, numere reprezentând numărul de puncte şi respectiv numărul de segmente;
• pe următoarele M linii, câte o pereche de numere distincte p1[1], p2[i] 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 cerc2.out va conține un singur număr P reprezentând numărul total de puncte de intersecţie formate în interiorul cercului. Dacă acest număr depăşeşte 999999, atunci se va scrie numărul format numai din ultimele sale 6 cifre.

Restricții și precizări

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

Exemplu:

cerc2.in

5 6
1 2
1 3
1 4
2 4
3 5
4 5

cerc2.out

3

Explicație

S-au format în interiorul cercului 3 puncte de intersecţie (marcate prin cerculeţe pe figura de mai jos).

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}")