\section{Задача E. <<Разделение королевства>>}

\begin{frame}[t]{Задача E. <<Разделение королевства>>}

  \begin{center}
    \LARGE Задача E. <<Разделение~королевства>>
  \end{center}

  $$\includegraphics[width=5cm]{pics/division.jpg}$$	
\end{frame}

\begin{frame}[t]{}
  \vspace{3cm}
  \begin{itemize}
    \item Идея задачи --- Анна Малова 
    \item Подготовка тестов --- Виталий Демьянюк 
    \item Разбор задачи --- Анна Малова 
  \end{itemize}
\end{frame}

\subsection{Постановка задачи}

\begin{frame}[t]{Постановка задачи}
Входные данные:

В королевстве $n$ замков, $i$-ый замок находится в точке $(x_i+0.5, y_i+0.5)$.
Необходимо разделить королевство так, чтобы выполнялись следующие условия:
\begin{itemize}
	\item После разделения любые два замка должны находится в разных частях королевства.
	\item Разделение производится прямыми, параллельными осям координат.
	\item Для горизонтальных прямых $x$, а для вертикальных $y$,
		координата всех точек на оси должна быть целым числом.
	\item Количество прямых не должно превышать $n - 1$.
\end{itemize}	
\end{frame}

\subsection{Решение}

\begin{frame}[t]{Решение}
\begin{itemize}
	\uncover<1->%
	{
	\item Отсортируем замки по $x$ координате, между каждой парой соседних замков проведем прямую. \\
	}
	\uncover<2->%
	{
	\item Посмотрим на замки, которые имеют одинаковую координату по $x$. \\
		Для каждого такого $x$ отсортируем замки по $y$ координате. Проведем прямую между каждой 
		парой соседних замков.
	}
	\uncover<3->%
	{
	\item Заметим, что при таком разделении, количество прямых не превышает $n - 1$.\\
	}
\end{itemize}
\end{frame}
