% Idee: Sandra Schumann
% Teostus: Jaagup Tamme

\documentclass[a4paper,11pt]{article}
\usepackage[et]{../../eio}
\usepackage{tikz}
\usetikzlibrary{calc,arrows.meta}

\begin{document}
\begin{ol}{\eio}{\fv 7.02.2026}{\yle}{}
\begin{yl}{3}{Puuvõrad}{vorad}{1 sek / 3 sek}{50 punkti}

Tahad saada Kaarsilla otsa juurest Deltasse, aga just hakas vihma ladistama. Oled tehtud suhkrust ja ei taha väga ära sulada. Seega pead võimalikult vähe maad läbima vihma käes.

Antud on Kaarsilla otsa ja Delta ukse koordinaadid ning seejärel hulk puuvõrasid: puuvõra on defineeritud kui keskpunkti koordinaat ja võra raadius. Puuvõra all oled vihma käest kaitstud.

Leia teekond Deltasse, millega pead kõige vähem maad läbima vihma käes.

\sis
Esimesel real on kaks tühikuga eraldatud täisarvu $K_x$ ja $K_y$ ($-10^9 \le K_x, K_y \le 10^9$), Kaarsilla otsa x- ja y-koordinaat.

Teisel real on kaks tühikuga eraldatud täisarvu $D_x$ ja $D_y$ ($-10^9 \le D_x, D_y \le 10^9$), Delta ukse x- ja y-koordinaat.

Kolmandal real on üks täisarv $N$ ($0 \le N \le 10^3$), see on puuvõrade arv.

Järgmisel $N$ real on igaühel kolm tühikuga eraldatud täisarvu $X_i$, $Y_i$ ja $R_i$ ($-10^9 \le X_i, Y_i \le 10^9, 1 \le R_i \le 10^9$), puuvõra number $i$ keskpunkti x- ja y-koordinaat ning selle puuvõra raadius.

\val
Esimesele reale väljastada üks täisarv $M$, nende lõikude arv, kus oled vihma käes.

Järgmisele $M$ reale väljastada igaühele üks vihma käes olemise lõik. Iga lõik väljastada eraldi real kahe tühikuga eraldatud sõnena $a$ ja $\ell$ ($a, \ell \in \{\texttt{Kaarsild}, \texttt{Delta}, 1, 2, \dots, N\} $), kus $a$ ja $\ell$ on lõigu algus ja lõpp ning \texttt{Kaarsild} tähistab Kaarsilda, \texttt{Delta} tähistab Deltat ja arv tähistab vastava numbriga puuvõra.

Väljastatud vastus loetakse õigeks, kui selle vihma käes viibimise teepikkus erineb optimaalsest kuni $0,0001\,\%$ võrra.

\hnd \testideraldi
\begin{xenum0}
  \item (0 punkti) \naitedlyhem
  \item (25 punkti) $N \le 3$.
  \item (25 punkti) \piiranguteta
\end{xenum0}

\clearpage

\nde[0]{3cm}{3cm}

\begin{tikzpicture}[scale=1]

  \draw[->] (-1.5,0) -- (6.5,0);
  \draw[->] (0,-1.5) -- (0,5.5);

  \draw[step=1, gray!30] (-1.5,-1.5) grid (6.5,5.5);

  \foreach \x in {-1,0,...,6}
    \node[below, font=\small] at (\x,0) {\x};
  \foreach \y in {-1,0,...,5}
    \node[left, font=\small] at (0,\y) {\y};

  \draw[thick, black!70!black] (3,1) circle (2);
  \fill (3,1) circle (2pt);
  \node[above] at (3,1) {1. puuvõra};

  \fill (3,4) circle (2pt);
  \node[above] at (3,4) {Delta};

  \fill[black!70!black] (0,1) circle (2pt);
  \node[above, black!70!black] at (0,1) {Kaarsild};

\end{tikzpicture}

Kaarsilla juurest otse Deltasse on $3\sqrt{2} \approx 4,24$ ühikut, kuid Kaarsilla juurest esimese puuvõra alla ja sealt Delta juurde liikudes oled vihma käes ainult $1 + 1 = 2$ ühikut.

\nde[1]{3cm}{3cm}

\begin{tikzpicture}[scale=1]

  \draw[->] (-1.5,0) -- (6.5,0);
  \draw[->] (0,-1.5) -- (0,5.5);

  \draw[step=1, gray!30] (-1.5,-1.5) grid (6.5,5.5);

  \foreach \x in {-1,0,...,6}
    \node[below, font=\small] at (\x,0) {\x};
  \foreach \y in {-1,0,...,5}
    \node[left, font=\small] at (0,\y) {\y};

  \draw[thick] (3,1) circle (2);
 \node[below] at (3,1) {1. puuvõra};

  \fill (3,1) circle (2pt);
  \node[above] at (3,1) {Delta};

  \fill (0,1) circle (2pt);
  \node[above] at (0,1) {Kaarsild};

\end{tikzpicture}

Liikumine on küll otse Delta suunas, kuid vihma käes oled ainult kuni esimese puuvõrani ja sealt edasi Delta juurde liigud puuvõra all.

\end{yl}
\end{ol}
\end{document}
