<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\begin{frame}
    \frametitle{\problemtitle}
    \begin{block}{Problem}
      Given $n\leq 1000$ line segments that partition the plane in small
      regions.
      Are there two regions the same \emph{distance} from the ocean?
    \end{block}
    \pause
    \begin{block}{Geometry solution}
      Find all intersections and construct the dual graph on faces:\\
      Costs $\mathcal O\left(n^2\log n\right)$ and your sanity ($256$ lines of C++).
    \end{block}
    \pause
    \begin{block}{Intended solution}
      \begin{itemize}
        \item The difference between adjacent distances is at most $1$.
        \item We can work modulo $2$ instead.
        \item The answer is \texttt{no} iff all pairs of adjacent faces have
          opposite values.
        \item I.e.: the dual graph must be bipartite.
        \item That's true iff in each intersection point an even number of
          lines meet.
        \item TODO
        \item Solution: check if each segment endpoint appears an even number of
          times in the input.
        \item Final complexity: $\mathcal O (n \log n)$ or $\mathcal O (n)$.
      \end{itemize}
    \end{block}
    \pause
    \solvestats
\end{frame}
</pre></body></html>