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

<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

1. 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))

1. Calcularea numarului de puncte de intersectie

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