Editing 2861 - puncte4

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