<filename>homework1/doc/closed_polyline.tex
\documentclass[a4paper,12pt,titlepage]{article}
\usepackage[utf8]{inputenc}
\usepackage[ukrainian]{babel}
\usepackage{tabulary}
\usepackage{amssymb}
\usepackage{threeparttable}
\usepackage{listings}

\title{
	Школа Аналізу Даних\\
	{\large Курс: "Алгоритми і структури даних"}\\[30pt]
	Домашня робота №1\\[1in]
}
\author{Підготував: <NAME>\\[3in]}
\date{\today}

\begin{document}

\maketitle

\tableofcontents

\newpage

%
% Task page
%

\section{Умова задачі}

На площині задано $N$ точок. Чи можна побудувати замкнену ламану без самоперетинів та самодотиків з вершинами тільки в заданих точках, яка з'єднує всі $N$ точок?

\vspace{15pt}
\noindent\textbf{\large Вхідні дані}
\vspace{4px}

Перший рядок вхідного файлу містить натуральне число $N(1 \leq N \leq 10^{5})$.
Кожний з наступних $N$ рядків містить пару цілих чисел $x_{i}, y_{i}$ -- координати $i$-ї точки$(-10^{5} \leq x_{i}, y_{i} \leq 10^{5})$.

\vspace{15pt}
\noindent\textbf{\large Вихідні дані}
\vspace{4px}

В першому рядку вихідного файлу виведіть \textbf{Yes} або \textbf{No} в залежності від того, чи існує шукана ламана. 
Якщо ламана існує виведіть в другому рядку $N$ цілих чисел через пробіл -- номера вершин ломаної в порядку обходу. 
Нумерація вершин починається з одиниці.

\vspace{15pt}
\noindent\textbf{\large Приклади}
\vspace{10px}


\noindent
\begin{tabulary}{10cm}{ |l|L| }
 \hline
 4 & Yes \\
 0 0 & 1 3 4 2 \\
 0 1 & \\
 1 0 & \\ 
 1 1 & \\ \hline
 3 & No \\
 0 0 & \\
 0 1 & \\
 0 2 & \\ \hline
\end{tabulary}


\newpage

%
% Solution page
%

\section{Алгоритм розв'язання}

Нехай $M$ - множина вхідних точок, $|M| = N$.\\
Опишемо алгоритм з \emph{низьким рівнем деталізації}.
\begin{enumerate}
	\item{
		Серед точок з $M$ виберемо дві точки $A$ та $B$.\\
		Введемо позначення $M' = M \backslash \{ A, B \}$.
	}
	\item{
		Проведемо уявну пряму $AB$, і розіб'ємо множину $M'$ на три підмножини:
		\begin{enumerate}
			\item{
				$M_{up}$ -- множина точок з $M'$, що знаходяться над прямою $AB$.
			}
			\item{
				$M_{on}$ -- множина точок з $M'$, що знаходяться на прямій $AB$.
			}
			\item{
				$M_{down}$ -- множина точок з $M'$, що знаходяться під прямою $AB$.
			}
		\end{enumerate}	
	}
	\item{
		В залежності від того які множини порожні маємо декілька варіантів:
		\begin{enumerate}
			\item{
				$M_{up} = M_{down} = \varnothing$\\
				Тоді зрозуміло що всі точки з $M$ знаходяться на прямій $AB$.\\
				І в такому випадку неможливо побудувати шукану ламану.
			}
			\item{
				$M_{up} = \varnothing$ або $M_{down} = \varnothing$\\
				Не порушуючи загальності візьмемо, що\\
				$M_{down} = \varnothing, M_{up} \neq \varnothing$\\
				Тоді включимо точки з $M_{on}$ до порожньої множини $M_{down}$\\
				$M_{down}' = M_{down} \cup M_{on} = \varnothing \cup M_{on} = M_{on}$\\
		    	$M_{up}' = M_{up}$
			}
			\item{
				$M_{up} \neq \varnothing, M_{down} \neq \varnothing$\\
				Тоді не важливо до якої множини включати точки з $M_{on}$.\\
		   	    Нехай це буде множина $M_{up}$, маємо:\\
		   	    $M_{down}' = M_{down}$\\
		   	    $M_{up}' = M_{up} \cup M_{on}$
			}
		\end{enumerate}
	}
	\item{
		Побудуємо верхню ламану $U$ на точках з $M_{up}'$, і окремо нижню ламану $D$ на точках з $M_{down}'$.
	}
	\item{
		Обєднаємо ламані $U$ та $D$ з вершинами $A$ та $B$, і отримаємо \emph{шукану замкнену ламану}.
	}
\end{enumerate}

\newpage

%
% Algo page
%

\section{Детелізація алгоритму}

Спробуємо деталізувати наш алгоритм, а саме відповісти на наступні запитання:

\begin{itemize}
	\item{за яким приципом обирати \emph{крайні точки} $A$, $B$?}
	\item{як будувати ламані $U$ та $D$?}
	\item{чому при обєднанні ламаних $U$ та $D$ утвориться ламана без самоперетинів та самодотиків?}
\end{itemize}

Для того, щоб зрозуміти принцип вибору точок $A$ та $B$, потрібно спочатку зрозуміти алгоритм побудови ламаних $U$ та $D$.\\

\subsection{Побудова верхньої ламаної}

Розглянемо алгоритм побудови верхньої ламаної $U$(алгоритм побудови нижньої ламаної $D$, буде аналогічний, за виключенням декількох деталей, які будуть зазначені).

\begin{enumerate}
	\item{Відсортуємо точки з $M_{up}'$ в порядку зростання значення їх координат(спочатку за першою, потім за другою).}
	\item{З'єднаємо точки в такому порядку, і отримаємо ламану $U$.}
\end{enumerate}

Зрозуміло, що отримана ламана $U$ не буде містити самоперетинів. Це легко довести від супротивного, припустивши що самоперетин існує, і розглянувши можливі варіанти розташування кінців ланок ламаної, що перетинаються.\\

\subsection{Вибір точок $A$ та $B$}

На даний момент, ми вже можемо дати відповідь на перше запитання, а саме. Оскільки в результаті ми маємо отримати верхню ламану з кінцями в точках $A$ та $B$, то ці точки мають бути на початку і в кінці відсортованого списку. Для визначеності вважатимемо, що точка $A$ -- на початку, а точка $B$ -- в кінці. Отже точка $A$ повинна мати мінімальні координати, а точка $B$ -- максимальні.\\

Оскільки алгоритм має властивість детермінованості, то будемо вибирати точку $A$, не тільки з найменшою першою координатою, але й з найменшою другою. Аналогічно $B$ -- точка з найбільшою першою координатою, і найбільшою другою. З точки зору геометріі, точка $A$ -- найнижча з найлівіших точок, а точка $B$ - найвища, з найправіших.\\

\subsection{Модифікації для нижньої ламаної}

Врато зазначити, як алгоритм побудови нижньої ламаної буде відрізнятися від алгоритму для верхньої. Виявляється, що різниця буде лише в тому, що сортувати точки потрібно по спаданню їх координат. Тоді перша точка в відсортованому списку буде точка $B$, а остання -- точка $A$. Завдяки цьому нам буде легко з'єднувати ламані, оскільки не прийдеться змінювати порядок вершин.\\

\subsection{Чому алгоритм правильний?}

Залишається відкритим лише третє питання, щодо того, чому взагалі описаний алгоритм буде давати правильну відповідь на задачу. А саме, потрібно показати, що утворена замкнена ламана, не буде містити самоперетинів та самодотиків. Зрозуміло, що якщо верхня ламана не має самоперетинів, і нижня ламана не має самоперетинів, то і утворена ламана не буде мати самоперетинів.\\

Для того, щоб показати, що утворена ламана не буде мати самодотиків, необхідно повернутися до побудови множин $M_{up}'$ та $M_{down}'$. Зрозуміло що самодотики можуть утворитися тільки в точках, що лежать на прямій $AB$. Але з побудови $M_{up}'$ та $M_{down}є$ випливає, що точки що лежать на прямій завжди будуть відноситися до однії з ламаних, і не буде такого, що одна точка буде в верхній ламаній, а інша в нижній.\\

Особливу увагу потрбіно приділити, випадку коли якась з множин $M_{up}$ чи $M_{down}$ буде порожньою. Тоді за алгоритмом побудови "розширених" множин, точки на прямій потраплять до порожньої ламаної, і ламана виродиться у відрізок $AB$. Важливо зрозуміти, що якби не було такого строгого розподілу точок на прямій, то можливий був би варіант, коли верхня ламана виродилася у відрізок, а нижня ламана містила б точку на прямій $AB$, і тоді б утворився самодотик. Але цей варіант неможливий, завдяки детермінованому алгоритму побудови "розширених" множин $M_{up}'$ та $M_{down}'$.

\subsection{Часткові випадки}

Дамо відповідь і на наступне запитання. Чи існують які небудь часткові випадки в яких алгоритм працювати не буде. Виявляється, що існують. А саме, випадок, коли \emph{не можливо} вибрати точки $A$ та $B$. Це можливо тільки тоді, коли $N = 1$. Оскільки задачею не регламентовано, то існування ламаної випливає з того, чи вважати замкненою ламаною одну точку. Для цього звернемося до \emph{Вікіпедії}:

\begin{quote}
A closed polygonal chain is one in which the first vertex coincides with the last one.
\end{quote} 

Отже будемо вважати одну точку, замкненою ламаною, що задовольняє умову.

\section{Складність алгоритму}

Для того, щоб оцінити алгоритм достаньо дати оцінку кожному з його пунктів, оскільки він вже розбитий на декілька незалежних частин.\\

\noindent
\begin{threeparttable}
	\begin{tabulary}{15cm}{ |p{10cm}|L| }
			\hline
			\textbf{Крок алгоритму} & \textbf{Часова складність} \\ \hline
			Вибір точок $A$ та $B$ & $O(1)$ \\ \hline
		Розбиття точок на множини $M_{up}', M_{down}'$ & $O(N)$ \\ \hline
		Сортування точок в множинах $M_{up}', M_{down}'$ & $O(NlogN)$\tnote{1}\\ \hline
		Побудова шуканої ламаної & $O(1)$ \\ \hline
		Загальна складність алгоритму & $O(NlogN)$ \\ 
		\hline
	\end{tabulary}
	\begin{tablenotes}
		\item[1] \textit{\smallВважаючи, що ми використовуємо сортування, що в найгіршому випадку мають часову складність $O(NlogN)$.}
	\end{tablenotes}
\end{threeparttable}\\[10px]

З таблиці видно, що загальна часова складність алгоритму становить $O(NlogN)$.\\

Говорячи про використану пам'ять, можна стверджувати, що алгоритм потребує $O(N)$ додаткової пам'яті, для побудови множин $M_{up}'$ та $M_{down}'$.

\newpage

\section{Реалізація на Java}

\lstinputlisting[language=Java]{/home/lionell/shad/algorithms/homework1/src/ClosedPolyline.java}

\end{document}