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

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>