View source for 2861 - puncte4

== Enunt == 

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

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

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

= Date de ieșire =
Fișierul de ieșire <code>puncte4OUT.txt</code> va conține <code>M</code> linii. Pe linia <code>i</code> va fi scris un număr natural reprezentând distanța la cel mai apropiat punct dintre cele <code>N</code> de pe hârtie pentru al <code>i</code>-lea punct de pe axa <code>OX</code> (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 =

* <code>1 ≤ N ≤ 100.000</code>
* <code>1 ≤ M ≤ 200.000</code>
* Toate coordonatele din fișierul de intrare sunt numere naturale din intervalul <code>[1, 1.000.000.000]</code>
* Cele <code>N</code> puncte din fișierul de intrare sunt sortate după coordonata <code>x</code> crescător, iar în cazul în care două puncte au aceeași abscisă, ele sunt ordonate crescător după coordonata <code>y</code>.
* Pentru <code>50%</code> din teste <code>N ≥ 90000</code> și <code>M ≥ 150000</code>.

= Exemplul 1: =
<code>puncte4IN.txt</code>
 3 2
 1 1 
 5 1
 10 2
 2
 7
<code>puncte4OUT.txt</code>
 2
 5

=== Explicație ===
Pe hârtie au fost desenate <code>3</code> puncte, având coordonatele <code>(1,1)</code>, <code>(5,1)</code>, respectiv <code>(10,2)</code>. Pe axa <code>OX</code> se află <code>2</code> puncte, având abscisa <code>2</code>, respectiv <code>7</code>.

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

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

== Exemplul 2: ==
<code>puncte4IN.txt</code>
 100001 2
 1 1 
 5 1
 10 2
 2
 7
<code>puncte4OUT.txt</code>
 Datele nu corespund restrictiilor impuse

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

# Constante
MAX_N = 100005
INF = float('inf')

# Definirea tipului punct ca un tuplu de două întregi
Point = Tuple[int, int]

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

# 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

# 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")

# Executarea programului
if __name__ == "__main__":
    main()

</syntaxhighlight>