Введение. 
Решение задачи с прикладным содержанием с применением программирования на языке высокого уровня

Цель работы — решение поставленной задачи: определить радиус и центр такой окружности, проходящей хотя бы через три различные точки заданного множества точек на плоскости, что минимальна разность количеств точек, лежащих внутри и вне окружности.

Цель работы определила следующие задачи исследования:

• 1. Провести анализ условия задачи и выработать подход к ее решению.
• 2. Выбрать наиболее подходящие представления для входных, выходных и промежуточных данных.
• 3. На основе выбранного подхода разработать алгоритм.
• 4. Описать алгоритм на языке программирования.
• 5. Составить тестовые примеры для отладки и демонстрации возможностей программы.

Анализ условия задачи и выработка подхода к ее решению

текстовый файл алгоритм данные По условию задачи исходными параметрами являются количество точек и их координаты в двумерном пространстве. В первую очередь необходимо организовать перебор троек точек из заданного множества. Порядок точек не важен, но чтобы сократить количество рассчитываемых наборов и не учитывать повторяющиеся наборы, упорядочим точки. Перебор для первой точки возможен только с 1 до n?2 (если n?2 точка является первой точкой набора, тогда n?1 — второй, а n — третьей), для второй точки перебор возможен со следующей координаты после выбранной в качестве первой до n?1, для третьей точки — со следующей координаты после выбранной в качестве после второй до n. Таким образом, мы сможем перебрать все возможные не повторяющиеся наборы из трех точек заданного множества.

Во время перебора точек мы по каждой тройке строим окружность и проверяем количество точек внутри и вне окружности. Принадлежность точки внутри и вне окружности проверяем с точностью ?. Во время проверки считаем количество точек внутри и вне окружности и находим разность этих количеств. Изначально разности присваиваем количество точек. Когда находится окружность с меньшей разностью, мы присваиваем наименьшей разности это значение и сохраняем координаты центра и радиус этой окружности. И так до конца перебора троек точек. В итоге мы найдем окружность построенную хотя бы по трем точкам с наименьшей разностью количеств точек внутри и вне окружности.

Окружность строим по следующему принципу:

Проведем через пары точек две прямые. Первая линия пусть проходит через P1 и P2, а прямая b — через P2 и P3.

Уравнения этих прямых будут:

;

где m — коэффициент наклона линии, получаемый из.

;

Центр круга — находится на пересечении двух перпендикулярных прямых, проходящих через середины отрезков P1P2 и P2 P3. Легко доказать, что прямая, перпендикулярная к линии с коэффициентом наклона m имеет коэффициент наклона -1/m, значит уравнения прямых, перпендикулярных a и b и проходящих через середины P1P2 и P2P3 будут.

Они пересекаются в центре, и решение относительно x дает.

Значение у вычислим подстановкой x в уравнение одного из перпендикуляров. Радиус найти элементарно. Например, P1 лежит на окружности и мы знаем центр. Радиус будет равен длине ОP1. Знаменатель (mb — ma) равен нулю, когда прямые параллельны. В этом случае они совпадают, то есть круга не существует. В конце организуем вывод параметром окружности и минимальную разность количеств точек.