Aurelia Raluca at 20:33, 23 February 2024

2024-02-23T20:33:52Z

Aurelia Raluca: Pagină nouă: == Enunt == Zăhărel a desenat pe o foaie de hârtie N puncte în plan. Curios din fire, şi-a ales încă M puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1) şi (x2, y2) este (x1-x2)2 + (y1-y2)2. == Cerința == Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M puncte...

2023-12-21T08:18:30Z

Pagină nouă: == Enunt == Zăhărel a desenat pe o foaie de hârtie N puncte în plan. Curios din fire, şi-a ales încă M puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1) şi (x2, y2) este (x1-x2)2 + (y1-y2)2. == Cerința == Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M puncte...

New page

== Enunt ==

Zăhărel a desenat pe o foaie de hârtie N puncte în plan. Curios din fire, şi-a ales încă M puncte pe axa OX şi s-a întrebat pentru fiecare dintre cele M puncte de pe axa Ox care dintre cele N puncte este cel mai apropiat (situat la distanță minimă). Se consideră că distanța dintre două puncte (x1, y1) şi (x2, y2) este (x1-x2)2 + (y1-y2)2.

== Cerința ==

Scrieți un program pentru Zăhărel care să determine pentru fiecare dintre cele M puncte de pe axa OX, care este distanța la cel mai apropiat punct dintre cele N desenate pe hârtie.

== Date de intrare ==

Fișierul de intrare puncte4.in conține pe prima linie numerele naturale N, M separate prin spații. Fiecare dintre următoarele N linii conține câte o pereche de numere naturale nenule x y, separate prin spații, reprezentând coordonatele celor N puncte (în ordinea abscisă, ordonată). Fiecare dintre următoarele M linii conține câte un număr natural x, reprezentând abscisele (coordonatele pe axa OX) ale celor M puncte.

== Date de ieșire ==

Fișierul de ieșire puncte4.out va conține M linii. Pe linia i va fi scris un număr natural reprezentând distanța la cel mai apropiat punct dintre cele N de pe hârtie pentru al i-lea punct de pe axa OX (considerând ordinea punctelor din fișierul de intrare).

== Restrictii si precizari ==

*1 ≤ N ≤ 100.000

*1 ≤ M ≤ 200.000

*Toate coordonatele din fișierul de intrare sunt numere naturale din intervalul [1, 1.000.000.000]

*Cele N puncte din fișierul de intrare sunt sortate după coordonata x crescător, iar în cazul în care două puncte au aceeași abscisă, ele sunt ordonate crescător după coordonata y.

*Pentru 50% din teste N ≥ 90000 și M ≥ 150000.

== Exemlul 1 ==

; intrare

:3 2

:1 1

:5 1

:10 2

:2

:7

; iesire

:Datele introduse corespund restrictiilor impuse.

:2

:5

== Exemplul 2 ==

; intrare

:-1 -9

:0 0

:11 16

:-7 -9

:3

:2

; iesire

:Datele de intrare nu corespund restrictiilor impuse.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">

#2861 - puncte4

import math

def distanta_puncte(punct1, punct2):
return (punct1[0] - punct2[0])**2 + (punct1[1] - punct2[1])**2

def cel_mai_apropiat_punct(punct_ox, lista_puncte):
dist_minima = float('inf')
punct_apropiat = None

for punct in lista_puncte:
distanta = distanta_puncte(punct_ox, punct)
if distanta < dist_minima:
dist_minima = distanta
punct_apropiat = punct

return math.sqrt(dist_minima)

def main():
# Citeste numarul de puncte N
N = int(input("Introduceti numarul de puncte pe hârtie: "))

# Citeste coordonatele punctelor N
puncte_hartie = []
for i in range(N):
x, y = map(int, input(f"Introduceti coordonatele punctului {i + 1} (x y): ").split())
puncte_hartie.append((x, y))

# Citeste numarul de puncte M de pe axa OX
M = int(input("Introduceti numarul de puncte de pe axa OX: "))

# Citeste coordonatele punctelor de pe axa OX
puncte_ox = [int(input(f"Introduceti coordonata punctului de pe axa OX {i + 1}: ")) for i in range(M)]

# Determina distanta la cel mai apropiat punct pentru fiecare punct de pe axa OX
for punct_ox in puncte_ox:
distanta_minima = cel_mai_apropiat_punct((punct_ox, 0), puncte_hartie)
print(f"Pt punctul de pe axa OX {punct_ox}, distanta la cel mai apropiat punct este {distanta_minima}")

if __name__ == "__main__":
main()

</syntaxhighlight>

2861 - puncte4 - Revision history

Aurelia Raluca at 20:33, 23 February 2024