RaulOtet: Pagină nouă: `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 t...

2024-07-25T12:35:47Z

Pagină nouă: <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 t...

New page

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

0749 - Cerc 2 - Revision history