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[edit | edit source]
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[edit | edit source]
Fișierul de intrare cerc2.in
conţine:
- pe prima linie două numere
N
şiM
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 distinctep1[1]
,p2[i]
despărţite prin câte un spaţiu, numere reprezentând capetele câte unui segment.
Date de ieșire[edit | edit source]
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[edit | edit source]
1 ≤ N ≤ 5000
0 ≤ M < 125000
1 ≤ p1[i] < p2[i] ≤ N
, numere naturale, oricarei
din{1,…, M}
- NU există perechi
p1[i] p2[i]
identice.
Exemplu:[edit | edit source]
cerc2.in
5 6 1 2 1 3 1 4 2 4 3 5 4 5
cerc2.out
3
Explicație[edit | edit source]
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
- 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>