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 puncte4IN.txt 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 puncte4OUT.txt 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). În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

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

Exemplul 1:

puncte4IN.txt

3 2
1 1 
5 1
10 2
2
7

puncte4OUT.txt

2
5

Explicație

Pe hârtie au fost desenate 3 puncte, având coordonatele (1,1), (5,1), respectiv (10,2). Pe axa OX se află 2 puncte, având abscisa 2, respectiv 7.

Distanța minimă dintre punctul de pe axa OX de abscisă 2 este 2 (cel mai apropiat punct fiind cel de coordonate (1,1)).

Distanța minimă dintre punctul de pe axa OX de abscisă 7 este 5 (cel mai apropiat punct fiind cel de coordonate (5,1)).

Exemplul 2:

puncte4IN.txt

100001 2
1 1 
5 1
10 2
2
7

puncte4OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> from typing import List, Tuple

1. Constante

MAX_N = 100005 INF = float('inf')

1. Definirea tipului punct ca un tuplu de două întregi

Point = Tuple[int, int]

1. Funcția pentru calculul punctului de întâlnire între două puncte

def meet(a: Point, b: Point) -> int:

   if a[0] == b[0]:
       return INF if a[1] < b[1] else 0
   x = (a[0]**2 + a[1]**2 - b[0]**2 - b[1]**2)
   x = (x + 2 * (a[0] - b[0]) - 1) // (2 * (a[0] - b[0]))
   return max(0, min(int(x), INF))

1. Funcția pentru verificarea restricțiilor

def verifica_restricții(N: int, M: int, puncte: List[Point]) -> bool:

   if not (1 <= N <= 100000) or not (1 <= M <= 200000):
       return False
   for x, y in puncte:
       if not (1 <= x <= 1000000000) or not (1 <= y <= 1000000000):
           return False
   return True

1. Funcția principală

def main():

   with open("puncte4IN.txt", "r") as fin, open("puncte4OUT.txt", "w") as fout:
       N, M = map(int, fin.readline().split())
       P = [tuple(map(int, fin.readline().split())) for _ in range(N)]
       
       # Verificarea restricțiilor
       if not verifica_restricții(N, M, P):
           fout.write("Datele nu corespund restrictiilor impuse\n")
           return

       X = [0] + [INF] * N
       stk = [0]
       
       for i in range(1, N):
           while stk and (x := meet(P[stk[-1]], P[i])) <= X[len(stk)-1]:
               stk.pop()
           stk.append(i)
           X[len(stk)-1] = x
           X[len(stk)] = INF

       for _ in range(M):
           x = int(fin.readline())
           i = next(i for i in range(len(stk)) if X[i] > x) - 1
           result = (x - P[stk[i]][0])**2 + P[stk[i]][1]**2
           fout.write(f"{result}\n")

1. Executarea programului

if __name__ == "__main__":

   main()

</syntaxhighlight>