Editing 2861 - puncte4 (section)

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